Binary Heap

A heap is a binary tree with two properties.

Properties

Completeness

Binary heaps are complete. I.e. packed to the left, every level filled except the bottom.

Partially ordered

The current node’s children have to have a value greater than the current one.

Implementation

Heaps can be implemented using arrays. This is possible because of the completeness of the heap.

We can order the nodes from top to bottom and left to right in value, matching the corresponding indices of the array as such:

Example in C++:

template <class T>
class MinHeap{
	private:
		int size; //number of current elements
		int capacity; //maximum capacity of the array
		T* arr; //the actual array in dynamic memory
	public: 
		...
}

template <class T>
MinHeap::MinHeap(int initcapacity) {
	size = 0;
	capacity = initcapcity;
	arr = new T[capacity];
}

Referencing nodes

The array is indexed from 0 to n - 1, where n is the number of nodes. Each level’s nodes are indexed from

$$2^{level}-1$$

to

$$2^{level+1}-2$$

where the root is level 0.

The children of a node i are the array elements indexed at

$$2i+1,2i+2$$

And the parent of a node i is the array element indexed at

$$\lfloor \frac{i-1}{2}\rfloor$$

There are also 1-indexed heaps that will use a slightly different calculation.

Operations

Insertion

On insertion the heap properties have to be maintained, much like a balanced tree type like the AVL tree. In this case, we’re concerned with the completeness of the tree, and its order.

The item is inserted at the bottom level in the first available space (in the array representation, it is pushed to the back of the array). This can be tracked using the heap size attribute that is present in the example implementation above. It is obviously of O(1) access using the array index at that size.

We then compare the value of the inserted node with it’s parent. For example, if we were inserting the 13th element of our heap, we would find the parent with the following:

$$\lfloor \frac{i-1}{2}\rfloor \leftrightarrow \frac{13-1}{2}=6$$

And then probably check the values programmatically with something like this:

if(child > parent){
	swap(child, parent)
}

We need to do this for every parent, so for grandparent and potentially higher up the tree. As such, our worst case scenario of operations on a binary heap is equivalent to the height of a complete tree, so the time complexity of the insert operation is:

$$O(\log n)$$

Deletion

For deletion, we need to find an appropriate replacement.

In a complete tree, we can just yoink the bottom right node to preserve the completeness of the tree. We then continually swap the node down until it falls into place, by comparing its value with that of its children. Something along the lines of:

if(curr->val < curr->left->val || curr->val < curr->right->val){
	if(curr->left->val > curr->right->val){
		swap(curr, curr->left);
	} else {
		swap(curr, curr->right); 
	}
} 
//else do nothing, it's already in place
 
//Or more concise with a ternary operator if you know both nodes exist:
 
Node* largest = curr->right->val > curr->left val ? curr->right : curr->left;
if(curr->val < largest){
	swap(curr, largest);
}
 
//Note that in the above examples, we assume swap() swaps the values, not the actual nodes.