Heaps are commonly implemented with an array.
Any binary tree can be stored in an array, but because a binary heap is
always a complete binary tree, it can be stored compactly. No space is
required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices.
void buildMaxHeap(int *arr, int length)
{
if (arr == nullptr || length < 1)
return;
for (int i = length / 2; i > 0; i--)
{
maxHeapify(arr, length, i);
}
}
void maxHeapify(int *arr, int length, int i)
{
int left = i * 2;
int right = i * 2 + 1;
int largest = i;
if (left < length && arr[largest] < arr[left])
largest = left;
if (right < length && arr[largest] < arr[right])
largest = right;
if (i != largest)
{
// swap the elements
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
maxHeapify(arr, length, largest);
}
}Insert
To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up), by following this algorithm:
- Add the element to the bottom level of the heap.
- Compare the added element with its parent; if they are in the correct order, stop.
- If not, swap the element with its parent and return to the previous step.
Time Complexit: O(log n)
Extract
The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap (also known as bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down, and extract-min/max).
- Replace the root of the heap with the last element on the last level.
- Compare the new root with its children; if they are in the correct order, stop.
- If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)
The downward-moving node is swapped with the larger of its children in a max-heap (in a min-heap it would be swapped with its smaller child), until it satisfies the heap property in its new position. This functionality is achieved by the maxHeapify function.
Time Complexit: O(log n)
