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 *arrint length)
{
	if (arr == nullptr || length < 1)
		return;
 
	for (int i = length / 2; i > 0; i--)
	{
		maxHeapify(arrlength, i);
	}
}
 
void maxHeapify(int *arrint lengthint 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(arrlength, largest);
	}
}

Insert

To add an element to a heap we must perform an up-heap operation (also known as bubble-uppercolate-upsift-uptrickle-upheapify-up, or cascade-up), by following this algorithm:

  1. Add the element to the bottom level of the heap.
  2. Compare the added element with its parent; if they are in the correct order, stop.
  3. 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-downpercolate-downsift-downtrickle downheapify-downcascade-down, and extract-min/max).

  1. Replace the root of the heap with the last element on the last level.
  2. Compare the new root with its children; if they are in the correct order, stop.
  3. 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)