A binary heap is a complete binary tree that satisfies the heap property. Notably two heaps can contain the same data but with items in different positions, the heap property allows multiple valid arrangements. Additionally, heaps can store the same value in multiple positions at the same time.

Binary heaps implement the same operations as a queue which is why they are typically used in their implementation. Specifically binary heaps implement the following operations:

• Insert: which adds an element with an associated priority to the heap.
• Extract Maximum/Minimum Removes the biggest or smallest element depending on implementation and returns it.

Abstract Data Type

Minimum Heap

template <class T>
class MinHeap {
	public:
		Heap(int initialCapacity);
	
		// Insert an element
		void insert(const T& element);
		
		// Remove and return from the root (minimum value)
		T removeMin();
}

Maximum Heap

template <class T>
class MinHeap {
	public:
		Heap(int initialCapacity);
	
		// Insert an element
		void insert(const T& element);
		
		// Remove and return from the root (maximum value)
		T removeMax();
}

Implementation

Resizable Array

Binary heaps despite being a representation of a tree are usually implemented using a resizable array. Where for a given node at index it's left child is placed at and it's right child is placed at .

Navigation Formulas

Given a node at index we can find nodes with the following formulae:

• Left Child:
• Right Child:
• Parent:

Operations

Insertion

When a new element is inserted into a binary heap, first the algorithm finds the first available leftmost leaf on the bottom level (preserving the completeness of the tree).

The partial ordering is fixed by comparing the new value to it's parent and recursively swapping them until the value is no longer greater than it's parent (this operation is called heapify up).

The worst case performance for a insertion operation is because we might need to swap every element up to the root ( operations) in the worst case.

Removing the Root

When we remove the root (ie. in a removeMin or removeMax) operation we start by copying the root so we can return it, we then replace the root node with the right-most leaf node (and remove the that leaf node from it's current position).

The partial ordering is fixed by comparing the new root to it's children and recursively swapping it with the largest child until the value is no longer greater than either of it's children (this operation is called heapify down). Finally the copied original root data is returned to the caller.

Similarly to insertion removing the root node is also as we might need to heapify down all the way to the leaf level ( operations) in the worst case.