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)