dsac::priority::HeapPriorityQueue< Entry, Compare > Class Template Reference

#include <heap_priority_queue.h>

Collaboration diagram for dsac::priority::HeapPriorityQueue< Entry, Compare >:

Public Member Functions
	HeapPriorityQueue ()
	Creates an empty priority queue.
	HeapPriorityQueue (const std::vector< Entry > &contents)
	Creates a priority queue populated with the given entries.
int	size () const
	Returns the current size of the priority queue.
bool	empty () const
	Returns true if the priority queue is empty.
const Entry &	min () const
	Returns a constant reference to the minimum entry.
void	insert (const Entry &e)
	Inserts a new entry into the priority queue.
void	remove_min ()
	Removes the minimum entry.

Protected Member Functions
int	parent (int j)
int	left (int j)
int	right (int j)
bool	has_left (int j)
bool	has_right (int j)
void	upheap (int j)
	Moves the entry at index j higher, if necessary, to restore the heap property.
void	downheap (int j)
	Moves the entry at index j lower, if necessary, to restore the heap property.
void	heapify ()

Protected Attributes
std::vector< Entry >	data
Compare	less_than

Constructor & Destructor Documentation

HeapPriorityQueue() [1/2]

template<typename Entry , typename Compare = std::less<Entry>>

dsac::priority::HeapPriorityQueue< Entry, Compare >::HeapPriorityQueue ( )

inline

Creates an empty priority queue.

HeapPriorityQueue() [2/2]

template<typename Entry , typename Compare = std::less<Entry>>

dsac::priority::HeapPriorityQueue< Entry, Compare >::HeapPriorityQueue ( const std::vector< Entry > &  contents )

inline

Creates a priority queue populated with the given entries.

Here is the call graph for this function:

Member Function Documentation

downheap()

template<typename Entry , typename Compare = std::less<Entry>>

void dsac::priority::HeapPriorityQueue< Entry, Compare >::downheap ( int  j )

inlineprotected

Moves the entry at index j lower, if necessary, to restore the heap property.

Here is the call graph for this function:

empty()

template<typename Entry , typename Compare = std::less<Entry>>

bool dsac::priority::HeapPriorityQueue< Entry, Compare >::empty ( ) const

inline

Returns true if the priority queue is empty.

has_left()

template<typename Entry , typename Compare = std::less<Entry>>

bool dsac::priority::HeapPriorityQueue< Entry, Compare >::has_left ( int  j )

inlineprotected

Here is the call graph for this function:

has_right()

template<typename Entry , typename Compare = std::less<Entry>>

bool dsac::priority::HeapPriorityQueue< Entry, Compare >::has_right ( int  j )

inlineprotected

Here is the call graph for this function:

heapify()

template<typename Entry , typename Compare = std::less<Entry>>

void dsac::priority::HeapPriorityQueue< Entry, Compare >::heapify ( )

inlineprotected

Here is the call graph for this function:

insert()

template<typename Entry , typename Compare = std::less<Entry>>

void dsac::priority::HeapPriorityQueue< Entry, Compare >::insert ( const Entry &  e )

inline

Inserts a new entry into the priority queue.

Here is the call graph for this function:

left()

template<typename Entry , typename Compare = std::less<Entry>>

int dsac::priority::HeapPriorityQueue< Entry, Compare >::left ( int  j )

inlineprotected

min()

template<typename Entry , typename Compare = std::less<Entry>>

const Entry & dsac::priority::HeapPriorityQueue< Entry, Compare >::min ( ) const

inline

Returns a constant reference to the minimum entry.

parent()

template<typename Entry , typename Compare = std::less<Entry>>

int dsac::priority::HeapPriorityQueue< Entry, Compare >::parent ( int  j )

inlineprotected

remove_min()

template<typename Entry , typename Compare = std::less<Entry>>

void dsac::priority::HeapPriorityQueue< Entry, Compare >::remove_min ( )

inline

Removes the minimum entry.

Here is the call graph for this function:

right()

template<typename Entry , typename Compare = std::less<Entry>>

int dsac::priority::HeapPriorityQueue< Entry, Compare >::right ( int  j )

inlineprotected

size()

template<typename Entry , typename Compare = std::less<Entry>>

int dsac::priority::HeapPriorityQueue< Entry, Compare >::size ( ) const

inline

Returns the current size of the priority queue.

upheap()

template<typename Entry , typename Compare = std::less<Entry>>

void dsac::priority::HeapPriorityQueue< Entry, Compare >::upheap ( int  j )

inlineprotected

Moves the entry at index j higher, if necessary, to restore the heap property.

Here is the call graph for this function:

Field Documentation

data

template<typename Entry , typename Compare = std::less<Entry>>

std::vector<Entry> dsac::priority::HeapPriorityQueue< Entry, Compare >::data

protected

less_than

template<typename Entry , typename Compare = std::less<Entry>>

Compare dsac::priority::HeapPriorityQueue< Entry, Compare >::less_than

protected

---

The documentation for this class was generated from the following file:

• dsac/priority/heap_priority_queue.h