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++) {
79 FW_ASSERT(parent < index, static_cast<FwAssertArgType>(parent), static_cast<FwAssertArgType>(index));
83 if (value <= this->m_heap[parent].value) {
87 this->m_heap[index] = this->m_heap[parent];
92 FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
93 FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
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++) {
166 FW_ASSERT(left > index, static_cast<FwAssertArgType>(left), static_cast<FwAssertArgType>(index));
167 FW_ASSERT(right > left, static_cast<FwAssertArgType>(right), static_cast<FwAssertArgType>(left));
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);
205 FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
206 FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
212 static_assert(not std::numeric_limits<FwSizeType>::is_signed,
"FwSizeType must be unsigned");
213 FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
214 FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
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) {
245 FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
246 FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
247 Node temp = this->m_heap[a];
248 this->m_heap[a] = this->m_heap[b];
249 this->m_heap[b] = temp;
bool pop(FwQueuePriorityType &value, FwSizeType &id)
Pop an item from the heap.
PlatformSizeType FwSizeType
~MaxHeap()
MaxHeap deconstructor.
bool isEmpty()
Is the heap empty?
bool push(FwQueuePriorityType value, FwSizeType id)
Push an item onto the heap.
MaxHeap()
MaxHeap constructor.
bool isFull()
Is the heap full?
C++-compatible configuration header for fprime configuration.
FwSizeType getSize() const
Get the current number of elements on the heap.
bool create(FwSizeType capacity)
MaxHeap creation.
PlatformQueuePriorityType FwQueuePriorityType