Os::MaxHeap Class Reference

A stable max heap data structure. More...

#include <Os/Pthreads/MaxHeap/MaxHeap.hpp>

Public Member Functions
	MaxHeap ()
	MaxHeap constructor. More...
	~MaxHeap ()
	MaxHeap deconstructor. More...
bool	create (NATIVE_UINT_TYPE capacity)
	MaxHeap creation. More...
bool	push (NATIVE_INT_TYPE value, NATIVE_UINT_TYPE id)
	Push an item onto the heap. More...
bool	pop (NATIVE_INT_TYPE &value, NATIVE_UINT_TYPE &id)
	Pop an item from the heap. More...
bool	isFull ()
	Is the heap full? More...
bool	isEmpty ()
	Is the heap empty? More...
NATIVE_UINT_TYPE	getSize ()
	Get the current number of elements on the heap. More...
void	print ()
	Print the contents of the heap to stdout. More...

Detailed Description

A stable max heap data structure.

This is a max heap data structure. Items of the highest value will be popped off the heap first. Items of equal value will be popped off in FIFO order. Insertion and deletion from the heap are both O(log(n)) time.

Definition at line 27 of file MaxHeap.hpp.

Constructor & Destructor Documentation

MaxHeap()

Os::MaxHeap::MaxHeap

(

)

MaxHeap constructor.

Create a max heap object

Definition at line 32 of file MaxHeap.cpp.

~MaxHeap()

Os::MaxHeap::~MaxHeap

(

)

MaxHeap deconstructor.

Free memory for the heap that was allocated in the constructor

Definition at line 40 of file MaxHeap.cpp.

Member Function Documentation

create()

bool Os::MaxHeap::create

(

NATIVE_UINT_TYPE

capacity

)

MaxHeap creation.

Create the max heap with a given maximum size

Parameters

capacity

the maximum number of elements to store in the heap

Definition at line 45 of file MaxHeap.cpp.

getSize()

NATIVE_UINT_TYPE Os::MaxHeap::getSize

(

)

Get the current number of elements on the heap.

This function returns the current number of items on the heap.

Definition at line 150 of file MaxHeap.cpp.

isEmpty()

bool Os::MaxHeap::isEmpty

(

)

Is the heap empty?

Is the heap empty? No item can be popped from the heap if this function returns true.

Definition at line 145 of file MaxHeap.cpp.

isFull()

bool Os::MaxHeap::isFull

(

)

Is the heap full?

Has the heap reached max size. No new items can be put on the heap if this function returns true.

Definition at line 140 of file MaxHeap.cpp.

pop()

bool Os::MaxHeap::pop	(	NATIVE_INT_TYPE &	value,
		NATIVE_UINT_TYPE &	id
	)

Pop an item from the heap.

The item with the maximum value in the heap will be returned. If there are items with equal values, the oldest item will be returned.

Parameters

value	the value of the element to popped from the heap
id	the identifier of the element popped from the heap

Definition at line 111 of file MaxHeap.cpp.

print()

void Os::MaxHeap::print

(

)

Print the contents of the heap to stdout.

This function here is for debugging purposes.

Definition at line 262 of file MaxHeap.cpp.

push()

bool Os::MaxHeap::push	(	NATIVE_INT_TYPE	value,
		NATIVE_UINT_TYPE	id
	)

Push an item onto the heap.

The item will be put into the heap according to its value. The id field is a data field set by the user which can be used to identify the element when it is popped off the heap.

Parameters

value	the value of the element to push onto the heap
id	the identifier of the element to push onto the heap

Definition at line 62 of file MaxHeap.cpp.

---

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

• Os/Pthreads/MaxHeap/MaxHeap.hpp
• Os/Pthreads/MaxHeap/MaxHeap.cpp