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

Private Member Functions
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...

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

Friends
template<class Type , class Comp >
std::ostream &	operator<< (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.

Todo:

Depending on your implementation, this function may or may 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

elems

The elements that should be placed in the heap.

Todo:

Construct a heap using the buildHeap algorithm

Member Function Documentation

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.

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

out	The stream to be written to.
toPrint	The 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:

• heap.h
• heap.cpp