26 #define LCHILD(x) (2 * x + 1)
27 #define RCHILD(x) (2 * x + 2)
28 #define PARENT(x) ((x - 1) / 2)
35 this->m_heap =
nullptr;
41 delete[] this->m_heap;
42 this->m_heap =
nullptr;
48 FW_ASSERT(capacity < std::numeric_limits<FwSizeType>::max());
49 this->m_heap =
new (std::nothrow) Node[capacity];
50 if (
nullptr == this->m_heap) {
53 this->m_capacity = capacity;
74 for (i = 0; (i < maxIter) && (index != 0); i++) {
83 if (value <= this->m_heap[parent].value) {
87 this->m_heap[index] = this->m_heap[parent];
96 this->m_heap[index].value = value;
97 this->m_heap[index].order = m_order;
98 this->m_heap[index].id = id;
114 value = this->m_heap[0].value;
115 id = this->m_heap[0].id;
123 this->m_heap[0] = this->m_heap[index];
135 return (this->m_size == this->m_capacity);
140 return (this->m_size == 0);
152 void MaxHeap::heapify() {
162 for (i = 0; (i < maxIter) && (index <= this->m_size); i++) {
172 if (left >= this->m_size) {
182 largest = this->max(left, largest);
185 if (right < this->m_size) {
188 largest = this->max(right, largest);
193 if (largest == index) {
198 this->swap(index, largest);
212 static_assert(not std::numeric_limits<FwSizeType>::is_signed,
"FwSizeType must be unsigned");
226 if (aValue == bValue) {
227 FwSizeType aAge = this->m_order - this->m_heap[a].order;
228 FwSizeType bAge = this->m_order - this->m_heap[b].order;
236 if (aValue > bValue) {
247 Node temp = this->m_heap[a];
248 this->m_heap[a] = this->m_heap[b];
249 this->m_heap[b] = temp;
PlatformAssertArgType FwAssertArgType
PlatformSizeType FwSizeType
PlatformQueuePriorityType FwQueuePriorityType
C++-compatible configuration header for fprime configuration.
MaxHeap()
MaxHeap constructor.
FwSizeType getSize() const
Get the current number of elements on the heap.
bool isFull()
Is the heap full?
~MaxHeap()
MaxHeap deconstructor.
bool isEmpty()
Is the heap empty?
bool pop(FwQueuePriorityType &value, FwSizeType &id)
Pop an item from the heap.
bool create(FwSizeType capacity)
MaxHeap creation.
bool push(FwQueuePriorityType value, FwSizeType id)
Push an item onto the heap.