Heap< MAX_HEAP, DATA_TYPE, SIZE_TYPE > Class Template Reference

Detailed Description

template<bool MAX_HEAP, typename DATA_TYPE, typename SIZE_TYPE = size_t>
class cy::Heap< MAX_HEAP, DATA_TYPE, SIZE_TYPE >

A general-purpose heap structure that allows random access and updates.

The main data can be kept in an external array or within the Heap class.

#include <cyHeap.h>

Public Member Functions
Constructor and Destructor
Initialization methods
void	Clear ()
	Deletes all data owned by the class.
void	CopyData (DATA_TYPE const *items, SIZE_TYPE itemCount)
	Copies the main data items from an array into the internal storage of this class.
void	MoveData (DATA_TYPE *items, SIZE_TYPE itemCount)
	Moves the main data items from an array to the internal storage of this class. Modifying this array externally can invalidate the heap structure. The given array must NOT be deleted externally. The given items pointer still points to the same data, but the class claims ownership of the data. Therefore, when the class object is deleted, the data items are deleted as well. If this is not desirable, use SetDataPointer.
void	SetDataPointer (DATA_TYPE *items, SIZE_TYPE itemCount)
	Sets the data pointer of this class. This method is used for sharing the items array with other structures. Unlike setting the main data using the MoveData method, when SetDataPointer is used, the class does NOT claim ownership of the data. Therefore, it does not deallocate memory used for the main data when it is deleted, and the data items must be deleted externally. However, the data items must NOT be deleted while an object of this class is used.
void	Build ()
	The Build method builds the heap structure using the main data. Therefore, the main data must be set using either CopyData, MoveData, or SetDataPointer before calling the Build method.
Access and manipulation methods
DATA_TYPE const &	GetItem (SIZE_TYPE id) const
	Returns the item from the main data with the given id.
bool	SetItem (SIZE_TYPE id, DATA_TYPE const &item)
	Sets the item with the given id and updates the heap structure accordingly. Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
bool	MoveItem (SIZE_TYPE id)
	Moves the item with the given id to the correct position in the heap. This method is useful for fixing the heap position after an item is modified externally. Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
bool	MoveItemUp (SIZE_TYPE id)
	Moves the item with the given id towards the top of the heap. This method is useful for fixing the heap position after an item is modified externally to increase its priority. Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
bool	MoveItemDown (SIZE_TYPE id)
	Moves the item with the given id towards the top of the heap. This method is useful for fixing the heap position after an item is modified externally to decrease its priority. Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
bool	RemoveItem (SIZE_TYPE id)
	Removes the item with the given id from the heap. Returns false if the item is not in the heap anymore (removed by Pop) or if its heap position is not changed.
bool	IsInHeap (SIZE_TYPE id) const
	Returns if the item with the given id is in the heap or removed by Pop.
SIZE_TYPE	NumItemsInHeap () const
	Returns the number of items in the heap.
bool	IsEmpty () const
	Returns false if there are no items in the heap.
bool	NotEmpty () const
	Returns true if there is any item in the heap.
DATA_TYPE const &	GetFromHeap (SIZE_TYPE heapIndex) const
	Returns the item from the heap with the given heap position. Note that items that are removed from the heap appear in the inverse order with which they were removed after the last item in the heap.
SIZE_TYPE	GetIDFromHeap (SIZE_TYPE heapIndex) const
	Returns the id of the item from the heap with the given heap position. Note that items that are removed from the heap appear in the inverse order with which they were removed after the last item in the heap.
DATA_TYPE const &	GetTopItem () const
	Returns the item at the top of the heap.
SIZE_TYPE	GetTopItemID () const
	Returns the id of the item at the top of the heap.
SIZE_TYPE	Pop (DATA_TYPE &item)
	Removes and returns the item at the top of the heap. The removed item is not deleted, but it is removed from the heap by placing it right after the last item in the heap.
SIZE_TYPE	Pop ()
	Removes the item at the top of the heap. The removed item is not deleted, but it is removed from the heap by placing it right after the last item in the heap.