Wednesday, May 29, 2013

Heap Data Structure

Heap is an efficient data structure used for managing data during execution of algorithms like heapsort and priority queue. It supports insert and extract min (or max) operations efficiently. Heap achieves this by maintaining a partial ordering on the data set. This partial ordering is weaker than the sorted order but stronger than random order. Heap is a binary tree in which key on each node dominates key of its children.

There are two variations of heap, min-heaps and max-heaps(as shown below).

                                    10  <  45,75                                      2001 > 1045,1175
                                    45  <  70,55                                      1045 > 70,55

Property of Heap

  1. Tree is completely filled on all levels except the lowest level which gets filled from left up to a point. So it can be viewed as nearly complete binary tree.
  2. Both heaps(min and max) satisfy a heap property. In max-heap, the max heap property is that key of each node is larger than key of its children nodes. A min-heap is organized the opposite way.
  3. Smallest element in min-heap is at the root. Largest element in max-heap is at the root.
  4. Heap is NOT a binary search tree (it is binary tree ). So binary search doesn't work on heap.

Heap Implementation

  1. Binary Tree : The obvious implementation of heap is binary tree (evident from above diagram). So each key will get stored in node with two pointers to its children. Height of heap is the height of root node; and height of a node is number of edges on the longest downward path from node to the leaf. So height of above trees are 3 ( lg8 ).
  2. Array : Nearly complete binary tree in case of heap enables it to represent it without any pointers. Data can be stored as an array of keys, and use the position of the keys to implicitly satisfy the role of the  pointers. To make things simpler 
         
Node(i)left = 2* Node(i)  
Node(i)Right = 2*Node(i)+1


       So as shown above, root of the tree is stored at the first position of the array, and its left and the                             
       right children in the second and third positions, respectively. Assumed that array starts with 
       index 1 to make calculations simpler. So left child of i sits in position and right child in 2i+1. This 
       way you can easily move around tree without pointers.        

           int first_child(int i){
               return 2*i;
           }
           
           int parent(int i){
              if(i == 1) return -1
              else return (int)i/2;
           } 

 So array representation of heap saves memory but is less flexible than tree implementation. Updating nodes in array implementation is not efficient. It helps to implement heap as array as its fully packed till last level. But it will not be so efficient for normal binary trees. 

Heap Construction

The fundamental point which needs to be taken care is; the heap property should be retained during each new insertion. Let's take case of above min-heap. Now assume that you want to add one more item to the heap with key 5.

Step 1 : Add 5 to the next slot. 
The new element will get added to the next available slot in the array. This  ensures the desired balanced shape of the heap-labeled tree, but heap property might no longer be valid.


Step 2 : Swap Node 5 and 70 to satisfy min-heap property. 
After swap min-heap property test passes for node 5. But min-heap property fails for the parent node of 5(colored node in above picture).


Step 3 : Swap node 45 with 5.
Now node with key 5 is satisfied as its children have key values > 5.


Step 4 : Swap root node with its left child.
Bingo. Heap is perfect now.



Insertion Complexity : Swap process takes constant time at each level. So each insertion takes at most O(log n) time.

Creation Complexity : Each insertion takes O(log n) time; then creation (or insertion of n nodes will take O(n log n) time.

Extracting Minimum from min-heap

Minimum of a min-heap sits at first position; so finding first minimum value is easy. Now tricky part is how to find next minimum element. 

To find next minimum; let's remove the first element. After this to make sure that binary tree is maintained, let's copy last element to the first position. This is required to ensured that tree is filled at all levels except the lowest level. But after this the heap property might go for a toss as now a bigger element may sit at root. Now the heap should re-arrange itself so that the min-heap property satisfies. 

Heapify:  This is process in which a dis-satisfied element bubbles-down to appropriate position. To achieve this the dominant child should be swapped with the root to push down the problem to the next level. This should be continued further till last level. 
Heapify operation for each element takes lgn steps (or height of tree) so complexity is O(log n) time. 

Java Implementation : link

Heapsort

Exchanging the minimum element with the last element and calling heapify repeatedly gives an O( n logn) sorting algorithm, named as Heapsort. It's worst case complexity is O( n logn ) time, which is best that can be expected from any sorting algorithm. It is an in-place sorting i.e. uses no extra memory 




No comments:

Post a Comment