Heaps fundamentals

In this post will learn heap fundamentals, which are very important for solving priority queue problems. Heap is a kind of data structure based on the complete tree principle. By definition, a complete binary search tree of N levels has at least 2^N-1 nodes in it. There two properties heap holds :

1. Structural property: This means every level of the heap will be completely full except the last level. The last level will be filled from left to right order.
2. Heap property: It means parent node will be either greater or smaller than its children nodes. There are two kinds of heaps based on second property:

Max Heap
Max heap maintains the property that every parent node is greater than its children. The root of the max heap is the greatest element.

heap fundamentals

Min Heap
Min heap maintains the property that every parent node is less than its children. The root of the min-heap is the least element.

min heap

Implementation Notes
Usually, heaps are implemented with an array, which eases traversing from child to parent and parent to child; and viewed as a tree. The height of a heap with n elements will be O(logN). 

Children of a parent node i are 2i and 2i+1.
Parent of a node i will be [i/2].

    private int parent(int pos) {
        return pos / 2;
    }
    
    private int leftChild(int pos){
        return (2 * pos);
    }

    private int rightChild(int pos){
        return (2 * pos) + 1;
    }
    

Given that multiply and divide by 2 can be very efficiently implemented by left and right shifting, these operations are very efficient.

Maximum elements in a heap with height h will be 2h-1 while the minimum number of elements in heap with the same height will be 2h-1+1 (One more than nodes with height h-1)

Heap operations

1. Insert an element in heap
To insert a new element in a heap, insert it as the leftmost position available. This new element may violate the heap property, for example, in a min-heap, the newly added element is less than the parent node. We have to push this newly added node to its correct position, this process is called a heapification.
Let’s take an example and see how it works.
insert in heap

    public void insert(int element) {
        if (size >= maxsize) {
            return;
        }

        Heap[++size] = element;
        int current = size;

        while (Heap[current] < Heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

The complexity of this procedure is for O(logn).

2. Pop from heap
The deletion of node is usually done at the root. To delete a root, replace the root node with the last node in heap and then do downshift. As the new node replacing root may violate heap property, we need to check with its children. In Max heap, check if new node is greater than both its children. If not then swap it with the largest child and then again repeat it till node replacing root finds its valid place.

Algorithm (This is for max heapify)

  1. Let i be the index which we doubt that might violate heap property.
  2. left = 2i, right = 2i+1, largest = a[i]
  3. Check if left child is with in array limits, if yes, check if it is greater than the a[i].
  4. If left is greater than a[i], then largest till now is left, largest = left.
  5. Check if right is with in array limit, if yes, check if it is greater than largest, then change the largest, largest = right.
  6. Swap largest and a[i].
  7. Now, repeat step 1 to 6 with largest, till we see an element which does not violate heap property.

Let’s take an example:
pop in heap

   public int pop() {
        int popped = Heap[1];
        Heap[1] = Heap[size--];
        minHeapify(1);
        return popped;
    }
    private void swap(int i, int j) {
        int tmp = Heap[i];
        Heap[i] = Heap[j];
        Heap[j] = tmp;
    }

    // Function to heapify the node at pos
    private void minHeapify(int pos){

        if (!isLeaf(pos)) {
            if (Heap[pos] > Heap[leftChild(pos)]
                    || Heap[pos] > Heap[rightChild(pos)]) {

                if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) {
                    swap(pos, leftChild(pos));
                    minHeapify(leftChild(pos));
                }
                else {
                    swap(pos, rightChild(pos));
                    minHeapify(rightChild(pos));
                }
            }
        }
    }

3. Building a heap from a given array of elements.
This operation can easily be done using the heapify methods explained above. 

  1. Start from the middle element of the array, let’s say i
  2. Heapify with given index.
  3. Decrease index by one. Repeat step 2 till we reach first element.
   public void minHeap() {
        for (int pos = (size / 2); pos >= 1; pos--) {
            minHeapify(pos);
        }
    }

The complexity of this procedure is O(n).

How this complexity becomes O(n) while for adding each node will need logn time to heapify and if there are n nodes, it should be O(nlogn). The complexity of the heapify method for a particular element depends on its position in the heap. It takes O(1) time when the node is a leaf node (which makes up at least half of the nodes) and O(log n) time when it’s at the root.
If the height of the heap is h, the number of nodes will be 2h. So 2h/2 = 2h-1 nodes never move. 2h-2 nodes move by one level and so on.

4. Heapsort
Heap sort combines property of both insertion sort (no extra space required) and merge sort (time complexity being O(nlogn)). It can be easily achieved by using the above two procedures.

  1. Build max heap from the given array, with complexity of O(n)
  2. Swap first and last element of the array. Last element is now at its proper position.
  3. Decrease the size of heap by 1 to be heapify.
  4. Heapify with first element of the array.
  5. Repeat step 2 , 3 and 4 until there are elements to be sorted.

The complexity of the above procedure is O(nlogn).

Problems based on heaps
Reference : http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844