lab_heaps
Precarious Priority Queues
heap< T, Compare > Class Template Reference

heap: A priority queue implemented as a heap. More...

#include <heap.h>

Public Member Functions

 heap ()
 Constructs an empty heap. More...
 
 heap (const std::vector< T > &elems)
 Constructs a heap from a vector of elements by copying the elements into the heap's storage and then running the buildHeap algorithm. More...
 
pop ()
 Removes the element with highest priority according to the higherPriority() functor. More...
 
peek () const
 Returns, but does not remove, the element with highest priority. More...
 
void push (const T &elem)
 Inserts the given element into the heap, restoring the heap property after the insert as appropriate. More...
 
void updateElem (const size_t &idx, const T &elem)
 Updates the element at the provided index of the heap array. More...
 
bool empty () const
 Determines if the given heap is empty. More...
 
void getElems (std::vector< T > &heaped) const
 
size_t root () const
 Helper function that returns the root index of this heap. More...
 

Private Member Functions

size_t leftChild (size_t currentIdx) const
 Helper function that returns the index of the left child of a node in the heap. More...
 
size_t rightChild (size_t currentIdx) const
 Helper function that returns the index of the right child of a node in the heap. More...
 
size_t parent (size_t currentIdx) const
 Helper function that returns the index of the parent of a node in the heap. More...
 
bool hasAChild (size_t currentIdx) const
 Helper function that determines whether a given node has a child. More...
 
size_t maxPriorityChild (size_t currentIdx) const
 Helper function that returns the index of the child with the highest priority as defined by the higherPriority() functor. More...
 
void heapifyDown (size_t currentIdx)
 Helper function that restores the heap property by sinking a node down the tree as necessary. More...
 
void heapifyUp (size_t currentIdx)
 Helper function that restores the heap property by bubbling a node up the tree as necessary. More...
 

Private Attributes

std::vector< T > _elems
 The internal storage for this heap. More...
 
Compare higherPriority
 Comparison functor. More...
 

Friends

class HeapNodeDescriptor< T, Compare >
 
template<class Type , class Comp >
std::ostreamoperator<< (std::ostream &out, const heap< Type, Comp > &toPrint)
 Prints the heap to an std::ostream. More...
 

Detailed Description

template<class T, class Compare = std::less<T>>
class heap< T, Compare >

heap: A priority queue implemented as a heap.

Author
Chase Geigle
Date
Fall 2012

Constructor & Destructor Documentation

◆ heap() [1/2]

template<class T , class Compare >
heap< T, Compare >::heap ( )

Constructs an empty heap.

not need modifying

◆ heap() [2/2]

template<class T , class Compare >
heap< T, Compare >::heap ( const std::vector< T > &  elems)

Constructs a heap from a vector of elements by copying the elements into the heap's storage and then running the buildHeap algorithm.

Parameters
elemsThe elements that should be placed in the heap.

Member Function Documentation

◆ empty()

template<class T , class Compare >
bool heap< T, Compare >::empty ( ) const

Determines if the given heap is empty.

Returns
Whether or not there are elements in the heap.

◆ hasAChild()

template<class T , class Compare >
bool heap< T, Compare >::hasAChild ( size_t  currentIdx) const
private

Helper function that determines whether a given node has a child.

Parameters
currentIdxThe index of the current node.
Returns
A boolean indicating whether the current node has a child or not.

◆ heapifyDown()

template<class T , class Compare >
void heap< T, Compare >::heapifyDown ( size_t  currentIdx)
private

Helper function that restores the heap property by sinking a node down the tree as necessary.

Parameters
currentIdxThe index of the current node that is being sunk down the tree.

◆ heapifyUp()

template<class T , class Compare >
void heap< T, Compare >::heapifyUp ( size_t  currentIdx)
private

Helper function that restores the heap property by bubbling a node up the tree as necessary.

Parameters
currentIdxThe index of the current node that is being bubbled up the tree.

◆ leftChild()

template<class T , class Compare >
size_t heap< T, Compare >::leftChild ( size_t  currentIdx) const
private

Helper function that returns the index of the left child of a node in the heap.

Required for grading purposes! (And it should be useful to you as well).

Parameters
currentIdxThe index of the current node.
Returns
The index of the left child of the current node.

◆ maxPriorityChild()

template<class T , class Compare >
size_t heap< T, Compare >::maxPriorityChild ( size_t  currentIdx) const
private

Helper function that returns the index of the child with the highest priority as defined by the higherPriority() functor.

For example, if T == int and the left child of the current node has data 5 and the right child of the current node has data 9, this function should return the index of the left child (because the default higherPriority() behaves like operator<).

This function assumes that the current node has children.

Parameters
currentIdxThe index of the current node.
Returns
The index of the highest priority child of this node.

as defined by higherPriority()

◆ parent()

template<class T , class Compare >
size_t heap< T, Compare >::parent ( size_t  currentIdx) const
private

Helper function that returns the index of the parent of a node in the heap.

Parameters
currentIdxThe index of the current node.
Returns
The index of the parent of the current node.

◆ peek()

template<class T , class Compare >
T heap< T, Compare >::peek ( ) const

Returns, but does not remove, the element with highest priority.

Returns
The highest priority element in the entire heap.

◆ pop()

template<class T , class Compare >
T heap< T, Compare >::pop ( )

Removes the element with highest priority according to the higherPriority() functor.

Returns
The element with highest priority in the heap.

◆ push()

template<class T , class Compare >
void heap< T, Compare >::push ( const T &  elem)

Inserts the given element into the heap, restoring the heap property after the insert as appropriate.

Parameters
elemThe element to be inserted.

◆ rightChild()

template<class T , class Compare >
size_t heap< T, Compare >::rightChild ( size_t  currentIdx) const
private

Helper function that returns the index of the right child of a node in the heap.

Required for grading purposes! (And it should be useful to you as well).

Parameters
currentIdxThe index of the current node.
Returns
The index of the right child of the current node.

◆ root()

template<class T , class Compare >
size_t heap< T, Compare >::root ( ) const

Helper function that returns the root index of this heap.

Required for grading purposes! (This function should be ridiculously easy: either return 0 if you plan to store the root at index 0, or 1 if you plan on storing it at index 1).

Returns
The index of the root node of the heap.

◆ updateElem()

template<class T , class Compare >
void heap< T, Compare >::updateElem ( const size_t &  idx,
const T &  elem 
)

Updates the element at the provided index of the heap array.

The update is done in such a way that the array will be corrected, so it will remain as a valid heap.

Parameters
idxThe index of the element to be updated (This is root()-indexed, so will work if using either zero or one-indexed heaps)
elemThe element to be updated with.

Friends And Related Function Documentation

◆ operator<<

template<class T , class Compare = std::less<T>>
template<class Type , class Comp >
std::ostream& operator<< ( std::ostream out,
const heap< Type, Comp > &  toPrint 
)
friend

Prints the heap to an std::ostream.

Given for you. Uses the helper functions below to do its work, so please implement them!

Parameters
outThe stream to be written to.
toPrintThe heap to be printed.

Member Data Documentation

◆ _elems

template<class T , class Compare = std::less<T>>
std::vector<T> heap< T, Compare >::_elems
private

The internal storage for this heap.

You may choose whether your heap is 0-based or 1-based (i.e., you are free to store the root at either index 0 or index 1). You should pick one, and write the helper functions according to that choice.

◆ higherPriority

template<class T , class Compare = std::less<T>>
Compare heap< T, Compare >::higherPriority
private

Comparison functor.

This functor takes two parameters and returns true if the first parameter has a higher priority than the second.

Compare is a template parameter and defaults to std::less, which creates a min-heap. So, if T = int and a = 3 and b = 5, higherPriority(a, b) = true (a < b, so a has higher priority) and higherPriority(b, a) = false (b > a, so b has lower priority)


The documentation for this class was generated from the following files: