Coding Recipies: Binary Heap

Problem Statement :

Discuss Binary Heap
a. Its properties.
b. Representation.
c. Operations supported.
d. Implementation.

Solution:
Please refer to full Source Code here

Explanation :

1. Concept :

A Binary Heap is a complete binary tree,
Binary heap can be of two Types :
1. Max heap : parent has higher priority than its children.
In this parent has higher priority than its children, since the parent has higher property it is called Max Binary Heap. Therefore , the largest will be at the root.
2. Min Heap : parent has lower priority than its children.
In this parent has lesser priority than its children, since the parent has lesser property it is called Min Binary Heap. Therefore , the minimum element will be at the root.

This is called heap order property.

What is complete binary tree ?
All the internal nodes of tree have 2 children , except the last 2 levels.
The last level will have nodes filled from left to right.

This is called heap structure property.

Binary Heap is used in the implementation of Priority Queue and Heapsort Algorithm.

Fig: a) Not a Binary Heap Fig b) Binary Heap

2. Representation(in Array):

For the easy of discussion we will be considering Max heap for all our discussion through out this post.
Binary Heap be implemented using Binary Tree or Array.
In case of array , for a parent located at index i , its childs are located at 2i and 2i +1 .
e.g. for a node at index 4 , its childs will be at 8 and 9.
Similarly , for any child its parent is located at (i / 2).
e..g. for a node at index 9 its parent will be at 4.

Note : The root of the tree will be located at index '0' .

Now lets represent the above complete tree in the form of array from the fig (b)

If you observe carefully , the elements of the array are arranged in the level order traversal of the tree.

3. Basic Operations Supported
      a) Insert :
                 In case of insertion of a node in a binary heap the node is added to last level and to the left most of the available positions.
   In the above complete tree the next node added will be left child of '4'

fig: Insertion of node

With insertion of 12 which has higher priority than its parent so it gets swapped up the tree in two steps i.e. with its ancestor 9 as well . So the final structure after 12 is inserted and 'Swim' operation is called to restore heap structure property

Fig: correct position of 12

With the addition of new Node in the binary heap , order heap property might be violated and we need to fix the proper position of the inserted node. This procedure of fixing up is called by many names like
'percolate up' , 'bubble up' , 'swim UP ' , 'heapify' . Here we will be using 'Swim'.

Insertion Algorithm:

Add the element to the end of the array
Shift the node up the tree until order heap property is not satisfied, we shift until node's value is greater than its parent.

To resolve this we will call a function called 'Swim' which will take this node above in the tree and will fix the order heap property.

        /**
  * Insert Key into Heap
  * @param val : key to be inserted in the heap
  * @throws HeapException : Incase Heap is full
  */
 public void insert(int val) throws HeapException{
  if(heapSize  == heap.length)
   throw new HeapException("Heap Leakage , Overflowing");
  else{
   System.out.println("Insert : " +val);
   heap[++heapSize]=val;
   swim(heapSize);
  }
 }

 private void swim(int index) {
  while(index > 1 && isLess(index/2, index))
  {
   swap(index/2 , index) ;
   index = index / 2 ;
  }
 }

b) Delete :

This operation deletes the max item from the heap, root is then replaced by last element of the array, which is then shifted down the tree until order heap property is satisfied, i.e., the node's value is higher than its children. We will use the 'Sink' function to shift the node down the tree.

Eg. Max element 17 is deleted


Fig1: 17 deleted , replaced by 6


Fig2: Higher value child 10 replaced 6


Fig3: Higher value child 8 replaced 6

Fig4: No swapping as 6 is higher than its child(s)

Deletion Algorithm:

Replace root with the last element.
Reduce heap size.
Shift the root , down the tree

a. If the root is smaller than any of its child , replace it with the higher child.
b. Repeat this process until node is higher than its child.

    /**
     * @return max Element from Heap and remove from heap
     */
 public int delMax(){
  int max=heap[1];
  heap[1] = heap[heapSize--] ;
  sink(1);
  return max;
 }

  /**
   * Sink down operation to 
   * @param index : index of the root
   */
 private void sink(int index) {
  while(2*index < heapSize) {

   int child= 2*index;  //first child

   if(child < heapSize && isLess(child, child + 1 )) // to pick the higher child
    child++; //second child

   if(!isLess(index, child)) //break if parent is higher than both children
    break;

   swap(index , child);
   index=child;
  }
 }

Note: I have left the index 0 empty for easy calculations, hence the root is located at index 1.
Note: For the root at index 0,
children are at (2*i + 1) and (2*i+2)
For the root at index 1
children are are at (2*i) and (2*i + 1)

Please refer to full Source Code here

Binary Heap uses:
1. Heap Sort
2. Priority Queue

Priority Queue (Brief Introduction)
Priority Queue is a data Structure which use the concept of Binary Heap Trees, it finds its application where processing of elements is based on some priority. Java has provided PriorityQueue class which implement Queue Interface. PriorityQueue has to implement Comparable or Comparator Interface, so that items can be compared with each other.

Below is the comparision of Time complexities.
Which clearly shows how good binary heaps are when finding the minimum or maximum is required

Please comment and if u have any suggestion or any optimized approach for the same.

Happy Coding !! :)

Coding Recipies

21 Oct 2013

Binary Heap

1 comment: