Foundations‎ > ‎Data Structures‎ > ‎Tree‎ > ‎

### Binary Heap

 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); } }````InsertTo 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)ExtractThe 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)`