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


bool  empty () const 
 Determines if the given heap is empty. More...



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.
 Todo:
 Depending on your implementation, this function may or may 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. 
 Todo:
 Construct a heap using the buildHeap algorithm
◆ 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.
 Todo:
 Remove, and return, the element with highest priority
◆ 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.
 Todo:
 Return, but do not remove, the element with highest priority
◆ 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. 
 Todo:
 Add elem to 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.
 Todo:
 Determine if the heap is empty
◆ root()
template<class T , class Compare >
size_t heap< T, Compare >::root 
( 
 ) 
const 

private 
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.
 Todo:
 Update to return the index you are choosing to be your root.
◆ 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.
 Todo:
 Update to return the index of the left child.
◆ 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.
 Todo:
 Update to return the index of the right child.
◆ 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.
 Todo:
 Update to return the index of the parent.
◆ 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.
 Todo:
 Update to return whether the given node has a child
◆ 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.
 Todo:
 Update to return the index of the child with highest priority as defined by higherPriority()
◆ 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. 
 Todo:
 Implement the heapifyDown algorithm.
◆ 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. 
◆ 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: