heap: A priority queue implemented as a heap.
More...
#include <heap.h>

 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...


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


T  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...



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...


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
◆ heap() [1/2]
template<class T , class Compare >
Constructs an empty heap.
not need modifying
◆ heap() [2/2]
template<class T , class Compare >
Constructs a heap from a vector of elements by copying the elements into the heap's storage and then running the buildHeap algorithm.
 Parameters

elems  The elements that should be placed in the heap. 
◆ 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

currentIdx  The 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

currentIdx  The 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

currentIdx  The 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

currentIdx  The 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

currentIdx  The 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

currentIdx  The 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 = std::less<T>>
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

elem  The 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

currentIdx  The 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

idx  The index of the element to be updated (This is root()indexed, so will work if using either zero or oneindexed heaps) 
elem  The element to be updated with. 
◆ operator<<
template<class T , class Compare = std::less<T>>
template<class Type , class Comp >
Prints the heap to an std::ostream.
Given for you. Uses the helper functions below to do its work, so please implement them!
 Parameters

out  The stream to be written to. 
toPrint  The heap to be printed. 
◆ _elems
template<class T , class Compare = std::less<T>>
The internal storage for this heap.
You may choose whether your heap is 0based or 1based (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 minheap. 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: