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