Types::MaxHeap Class Reference

A stable max heap data structure. More...

#include <Os/Generic/Types/MaxHeap.hpp>

Public Member Functions
	MaxHeap ()
	MaxHeap constructor.
	~MaxHeap ()
	MaxHeap deconstructor.
bool	create (FwSizeType capacity)
	MaxHeap creation.
bool	push (FwQueuePriorityType value, FwSizeType id)
	Push an item onto the heap.
bool	pop (FwQueuePriorityType &value, FwSizeType &id)
	Pop an item from the heap.
bool	isFull ()
	Is the heap full?
bool	isEmpty ()
	Is the heap empty?
FwSizeType	getSize () const
	Get the current number of elements on the heap.

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.

Warning

allocates memory on the heap

Definition at line 28 of file MaxHeap.hpp.

Constructor & Destructor Documentation

MaxHeap()

Types::MaxHeap::MaxHeap

(

)

MaxHeap constructor.

Create a max heap object

Definition at line 32 of file MaxHeap.cpp.

~MaxHeap()

Types::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 Types::MaxHeap::create

(

FwSizeType

capacity

)

MaxHeap creation.

Create the max heap with a given maximum size

Warning

allocates memory on the heap

Parameters

capacity

the maximum number of elements to store in the heap

Definition at line 45 of file MaxHeap.cpp.

getSize()

FwSizeType Types::MaxHeap::getSize

(

)

const

Get the current number of elements on the heap.

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

Definition at line 144 of file MaxHeap.cpp.

isEmpty()

bool Types::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 139 of file MaxHeap.cpp.

isFull()

bool Types::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 134 of file MaxHeap.cpp.

pop()

bool Types::MaxHeap::pop	(	FwQueuePriorityType &	value,
		FwSizeType &	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 105 of file MaxHeap.cpp.

push()

bool Types::MaxHeap::push	(	FwQueuePriorityType	value,
		FwSizeType	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 57 of file MaxHeap.cpp.

---

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

• Os/Generic/Types/MaxHeap.hpp
• Os/Generic/Types/MaxHeap.cpp