kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT > Class Template Reference

Implements a max heap data structure, see http://en.wikipedia.org/wiki/Binary_heap. More...

#include <MaxHeap.h>

List of all members.

Public Member Functions
bool	MaxHeapify (int i)
	MaxHeapifies one node of the heap at index i and recursively calls itself to MaxHeapify the child nodes, so that all child nodes also satisfy the MaxHeap property.
void	KeyIncreased (int i)
	Call this after increasing the key at index i (giving a bigger priority to element at index i).
void	Insert (const T &value)
	Inserts a new value into the MaxHeap and works out the proper position for it in the queue.
void	PopFront ()
	Removes the item that is front of the queue. UDB if the queue is empty.
void	PopBack ()
	Removes the item that is back of the queue. UDB if the queue is empty.
const T &	Front () const
	Gives access to the frontmost item. UDB if the queue is empty.
const T &	Back () const
	Gives access to the item with lowest priority. Running time is O(logN). UDB if the queue is empty.
int	LowestPriorityIndex () const
int	Size () const
	How many elements are in the queue total.
void	Reserve (int size)
	As the underlying data structure is an array, you can use this to preallocate space.
int	Search (const T &value)
	Looks whether an item that is equal with respect to the PriorityCmp is present in the MaxHeap.
Static Public Member Functions
static int	ParentIndex (int i)
	Gives the index of the parent of the element at index i, or 0 if i==0 (i is the root).
static int	LeftChildIndex (int i)
	Gives the left child of the element at index i. Note that this will address out-of-bounds if there is no child.
static int	RightChildIndex (int i)
	Gives the right child of the element at index i. Note that this will address out-of-bounds if there is no child.
Public Attributes
Array< T, AllocT >	data
	Gives access to the queue as a linear array form.

---

Detailed Description

template<typename T, typename PriorityCmp = sort::TriCmpObj<T>, typename EqualCmp = sort::TriCmpObj<T>, typename LookupNotify = EmptyLookupNotify<T>, typename AllocT = StdCAlloc>
class kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >

Implements a max heap data structure, see http://en.wikipedia.org/wiki/Binary_heap.

MaxHeap is a (binary) heap structure that can be used as a priority queue. The PriorityCmp object is used to perform comparisons between elements.

int PriorityCmp(const T &a, const T &b); Returns <0 if a<b and b has a bigger priority. Returns >0 if a>b and a has a bigger priority. Returns 0 if it is indifferent in which order the elements come out of the priority queue. Returning 0 doesn't mean that the elements need to be the same however.

int EqualCmp(const T &a, const T &b); Returns 0 if the elements are equal, != 0 if not. If equal priority <=> equal elements, then you can use PriorityCmp as EqualCmp.

---

Member Function Documentation

template<typename T , typename PriorityCmp , typename EqualCmp , typename LookupNotify , typename AllocT >

bool kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::MaxHeapify

(

int

i

)

MaxHeapifies one node of the heap at index i and recursively calls itself to MaxHeapify the child nodes, so that all child nodes also satisfy the MaxHeap property.

Parameters:

i

The index of the element to start MaxHeapifying at.

Returns:

True if changes (swaps) needed to be made to the heap at the given position, false otherwise.

References kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::data, kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::LeftChildIndex(), and kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::RightChildIndex().

Referenced by kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::KeyIncreased(), and kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::PopFront().

template<typename T , typename PriorityCmp , typename EqualCmp , typename LookupNotify , typename AllocT >

void kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::KeyIncreased

(

int

i

)

Call this after increasing the key at index i (giving a bigger priority to element at index i).

This will re-maxheapify the structure and keep it intact.

References kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::MaxHeapify(), and kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::ParentIndex().

Referenced by kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::Insert(), and kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::PopBack().

template<typename T , typename PriorityCmp , typename EqualCmp , typename LookupNotify , typename AllocT >

void kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::Insert

(

const T &

value

)

Inserts a new value into the MaxHeap and works out the proper position for it in the queue.

Running time is O(logn).

References kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::data, and kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::KeyIncreased().

template<typename T , typename PriorityCmp , typename EqualCmp , typename LookupNotify , typename AllocT >

int kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::LowestPriorityIndex

(

)

const

Returns:

The index of the element with the lowest priority. UDB if queue is empty.

References kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::data.

Referenced by kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::Back(), and kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::PopBack().

template<typename T , typename PriorityCmp = sort::TriCmpObj<T>, typename EqualCmp = sort::TriCmpObj<T>, typename LookupNotify = EmptyLookupNotify<T>, typename AllocT = StdCAlloc>

int kNet::MaxHeap< T, PriorityCmp, EqualCmp, LookupNotify, AllocT >::Search

(

const T &

value

)

[inline]

Looks whether an item that is equal with respect to the PriorityCmp is present in the MaxHeap.

Running time is O(n).

Returns:

The index of the element where the first equaling item was found, or -1 if none was found.

---

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

• C:/knet/include/kNet/MaxHeap.h