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

heap< T, Compare >::heap

(

)

Constructs an empty heap.

heap() [2/2]

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

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.

Member Function Documentation

empty()

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

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

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

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

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

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

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.

parent()

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

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

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

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

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

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

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 one-indexed heaps)
elem	The 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

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 file:

• src/heap.h