Files Class List
Heap< DATA_TYPE, SIZE_TYPE > Class Template Reference

Detailed Description

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

A general-purpose max-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
 Heap ()
 
 ~Heap ()
 
Initialization methods
void Clear ()
 
void CopyData (const DATA_TYPE *items, SIZE_TYPE itemCount)
 
void MoveData (DATA_TYPE *items, SIZE_TYPE itemCount)
 
void SetDataPointer (DATA_TYPE *items, SIZE_TYPE itemCount)
 
void Build ()
 
Access and manipulation methods
const DATA_TYPE & GetItem (SIZE_TYPE id) const
 
bool SetItem (SIZE_TYPE id, const DATA_TYPE &item)
 
bool MoveItem (SIZE_TYPE id)
 
bool MoveItemUp (SIZE_TYPE id)
 
bool MoveItemDown (SIZE_TYPE id)
 
bool IsInHeap (SIZE_TYPE id) const
 
SIZE_TYPE NumItemsInHeap () const
 
const DATA_TYPE & GetFromHeap (SIZE_TYPE heapIndex) const
 
SIZE_TYPE GetIDFromHeap (SIZE_TYPE heapIndex) const
 
const DATA_TYPE & GetTopItem () const
 
SIZE_TYPE GetTopItemID () const
 
void Pop (DATA_TYPE &item)
 
void Pop ()
 

Member Function Documentation

§ Clear()

void Clear ( )

Deletes all data owned by the class.

§ CopyData()

void CopyData ( const DATA_TYPE *  items,
SIZE_TYPE  itemCount 
)

Copies the main data items from an array into the internal storage of this class.

§ MoveData()

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.

§ 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.

§ Build()

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.

§ GetItem()

const DATA_TYPE& GetItem ( SIZE_TYPE  id) const

Returns the item from the main data with the given id.

§ SetItem()

bool SetItem ( SIZE_TYPE  id,
const DATA_TYPE &  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.

§ MoveItem()

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.

§ MoveItemUp()

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.

§ MoveItemDown()

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.

§ IsInHeap()

bool IsInHeap ( SIZE_TYPE  id) const

Returns if the item with the given id is in the heap or removed by Pop.

§ NumItemsInHeap()

SIZE_TYPE NumItemsInHeap ( ) const

Returns the number of items in the heap.

§ GetFromHeap()

const DATA_TYPE& 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.

§ GetIDFromHeap()

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.

§ GetTopItem()

const DATA_TYPE& GetTopItem ( ) const

Returns the item at the top of the heap.

§ GetTopItemID()

SIZE_TYPE GetTopItemID ( ) const

Returns the id of the item at the top of the heap.

§ Pop() [1/2]

void 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.

§ Pop() [2/2]

void 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.