Binary Heap (Part 1)

At first enlighten yourself about Heap. Heap is a tree based data structure with heap property. Binary Heap is a very common implementation of heap data structures. Once you learn Binary Heap your eagerness to learn some advance Heap data structures will definitely increase. Two other advance heap data structures are Binomial Heap and Fibonacci Heap. In this article we will cover binary heap property, operations, implementation and it's possible applications.

Heap Property: If P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node.

Example of a Binary Max-Heap:

Binary Heap Properties:
  1. Heap Property: It's obvious to have this property. Otherwise it won't be a heap data structure. Right ?
  2. Shape Property: Binary Heap is a Complete Binary Tree. All levels are completely filled except possibly the last level and the last level has all keys as left as possible
Binary Heap Operations:
Operation Complexity
getMin() / peek() O(1)
extractMin() O(lg n)
insert() O(lg n)
decreaseKey() O(lg n)
delete() O(lg n)
Implementation:

In this section we will try to implement a Binary Min-Heap. As you know Binary Heap is a Complete Binary Tree, we can store this tree in an array. Root node resides at index 1. In general if parent is in index x, left child located at index 2x and right child located at index 2x+1. Also if a node resides in index x, parent will be x/2. So for any node x here is three utility methods to get index of parent, left child and right child.

private static int parent(int i) { return (i / 2); }

private static int left(int i) { return (2 * i); }

private static int right(int i) { return (2 * i + 1); }

Our BinaryHeap class has three variables. heapArr[], heapSize and capacity. Capacity will be provided into constructor while making instance of the class. heapArr[] will be initialized based on capacity. heapSize tracks current number of elements in binary heap.

static class BinaryMinHeap {
    int heapArr[];              // Root node index is 1
    int heapSize;
    int capacity;

    BinaryMinHeap(int capacity) {
        this.capacity = capacity;
        heapArr = new int[capacity+1];
        heapSize = 0;
    }
}

Insert Operation:

This is comparatively easy operation of binary heap. Add new key as a last element of tree. Then iteratively push it up based on heap property (min/max heap). As we are building min-heap if parent of node x if greater than x, swap keys of node x and it's parent and then go to parent. Do the same until heap property satisfied.

// Complexity: O(lg n)
public void insertItem(int item) {
    if(heapSize == capacity) return;
    heapSize++;
    heapArr[heapSize] = item;
    int currentNode = heapSize;
    int parentNode = parent(currentNode);

    while(currentNode != 1 && heapArr[parentNode] > heapArr[currentNode]) {
        int t = heapArr[parentNode];
        heapArr[parentNode] = heapArr[currentNode];
        heapArr[currentNode] = t;
        currentNode = parentNode;
        parentNode = parent(currentNode);
    }
}

Get Min / Peek:

No need to describe anything I guess. root contains desired value. Correct ?

// Complexity: O(1)
public int getMin() {
    return heapArr[1];
}

Extract Min:

Extract min operation return minimum value of the heap (maximum value in case of max-heap) and then remove it from heap as well. To implement this operation we need another operation heapify(int parent) which is the heart of binary heap. Later you will see this operation will be used in some other operations. Since we are building min-heap we will call it minHeapify(int parent). So what it does actually ? Given a binary tree that doesn't maintain heap property it will convert the tree into proper binary heap.

Now lets focus to implement extractMin() operation. It has only 2 steps. At first copy the key of last element of the tree into root element. Then call minHeapify(int index) to make tree into proper binary heap. First step has constant complexity O(1) and then minHeapify(int parent) has complexity O(lg n). Thus final complexity is O(lg n).

// Complexity: O(lg n)
public int extractMin() {
    if(heapSize == 0) return Integer.MAX_VALUE;
    if(heapSize == 1) {
        heapSize--;
        return heapArr[1];
    }

    int root = heapArr[1];
    heapArr[1] = heapArr[heapSize];
    heapSize--;
    minHeapify(1);

    return root;
}

It's time to implement minHeapify(int parent) method. As you notice this method has parameter parent which denotes from which node it will start heapify. At first it will find left and right child index and then find index of smallest (largest in case of max-heap) key among parent, left and right child. If any of left and right child contain smallest key, swap with parent and then call minHeapify(int parent) again with index of smallest key.

private void minHeapify(int parent) {
    int l = left(parent);
    int r = right(parent);
    int smallest = parent;
    if (l <= heapSize && heapArr[l] < heapArr[smallest]) smallest = l;
    if (r <= heapSize && heapArr[r] < heapArr[smallest]) smallest = r;
    if (smallest != parent) {
        int t = heapArr[parent];
        heapArr[parent] = heapArr[smallest];
        heapArr[smallest] = t;
        minHeapify(smallest);
    }
}

Decreasing a key:

Consider there is a binary heap already built in and it looks like following. How about if want to decrease value of any key ? We are going to change 50 to 5. Then we need to rearrange nodes to maintain heap property. How to do that ? It's simple. Replace 50 by 5 and then pushing it up until reaches it's proper position. Here it will go up to root. Please notice decreasing a key operation needed for min-heap and increasing a key needed in max-heap.

        10                               5        
      /    \                          /    \         
     20     30          --->         10     30         
   /   \   /  \                    /   \   /  \       
  40   50 60  70                  40   20 60  70    
// Complexity: O(lg n)
public void decreaseItem(int index, int newVal) {
    heapArr[index] = newVal;
    int parentNode = parent(index);
    while(index != 1 && heapArr[parentNode] > heapArr[index]) {
        int t = heapArr[parentNode];
        heapArr[parentNode] = heapArr[index];
        heapArr[index] = t;
        index = parentNode;
        parentNode = parent(index);
    }
}

Deleting a key:

Deleting a key from binary heap is real tough. Just kidding !!! Actually deleting a key from binary heap requires 2 lines of code/operation. Suppose you want to delete item at index x. Decrease it's value to lowest integer possible. That's Integer.MIN_VALUE. Since it's lowest value of all integer it will go to root position when decreaseItem(int index, int newVal) execution done. Afterwards extract then root invoking extractMin() method.

// Complexity: O(lg n)
public void deleteItem(int index) {
    // Assign lowest value possible so that it will reach to root
    decreaseItem(index, Integer.MIN_VALUE);
    // Then extract min will remove that item from heap tree. correct ?
    extractMin();
}

Full Code: BinaryHeap_Demo.java

Application of BinaryHeap:
  1. Priority Queue: Any Heap data structure could be used as priority queue and priority queue is essential in some other algorithms like - BFS, Dijkstra, Huffman Coding
  2. HeapSort: HeapSort is very efficient sorting algorithm and binary heap could be used for heap sort.
  3. K'th Smallest/Largest Element: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.
References:
  1. https://en.wikipedia.org/wiki/Introduction_to_Algorithms
  2. https://en.wikipedia.org/wiki/Heap_(data_structure)
  3. https://en.wikipedia.org/wiki/Binary_heap
Blog Comments powered by Disqus.

Next Post Previous Post