BinaryHeap


Node.java

 package com.nrs.ds.basic.queue.heap;  
 public class Node {  
      public int iData;  
      public Node(int key){  
           iData = key;  
      }  
 }

HeapImpl.java

 package com.nrs.ds.basic.queue.heap;  
 public class HeapImpl {  
      private Node[] heapArray;  
      private int maxSize;  
      private int currentSize;  
      public HeapImpl(int mx){  
           maxSize = mx;  
           currentSize= 0;  
           heapArray= new Node[maxSize];  
      }  
      public boolean isEmpty(){  
           return (currentSize == 0);  
      }  
      public boolean insert(int key){  
           //if array is full failure  
           if(currentSize == maxSize){  
                return false;  
           }  
           //make a new node put it at the end, trickle it up  
           Node newNode = new Node(key);   
           heapArray[currentSize] = newNode;  
           trickleUp(currentSize++);  
           return true;  
      }  
      public void trickleUp(int index) {  
           int parent = (index-1) /2;  
           Node bottom = heapArray[index];  
           while((index >0) && (heapArray[parent].iData < bottom.iData) ){  
           //move node to down , move index up , parent <- its parent       
           heapArray[index] = heapArray[parent];  
           index = parent;  
           parent = (parent - 1) /2;  
           }  
           heapArray[index] = bottom;  
      }  
      public Node remove(){  
           //delete item with max key (assume non-empty list),  
           //save the root root <- last , trckle down the root , return removed node.  
           Node root = heapArray[0];  
           heapArray[0] = heapArray[--currentSize];  
           trickleDown(0);  
           return root;  
      }  
      public void trickleDown(int index) {  
           // save root, while node has at least one child, find larger child  
           //(rightChild exists?) , top .= largerChild? , shift child up , go down. index <- root  
           int largerChild;  
           Node top = heapArray[index];  
           while( index < currentSize /2){  
                int leftChild = 2*index+1;  
                int rightChild = leftChild+1;  
                if(rightChild < currentSize && heapArray[leftChild].iData < heapArray[rightChild].iData){  
                     largerChild = rightChild;  
                }else{  
                     largerChild = leftChild;  
                }  
                if(top.iData >= heapArray[largerChild].iData)  
                     break;  
                heapArray[index] = heapArray[largerChild];  
                index = largerChild;  
           }  
           heapArray[index] = top;  
      }  
      public boolean change(int index, int newValue){  
 //remember old, change to new , if raised, trickle it up, if lowered, trickle it down.  
           if(index<0 || index >= currentSize)  
                return false;  
           int oldValue = heapArray[index].iData;  
           heapArray[index].iData = newValue;  
           if(oldValue < newValue)  
                trickleUp(index);  
           else  
                trickleDown(index);  
           return true;  
      }  
      public void displayHeap(){  
           System.out.print("heapArray: ");  
           for(int m=0; m<currentSize; m++){  
                if(heapArray[m] != null)  
                     System.out.print( heapArray[m].iData + " ");  
                else  
                     System.out.print( "-- ");  
           }  
           System.out.println();  
           int nBlanks = 32;  
           int itemsPerRow = 1;  
           int column = 0;  
           int j = 0;  
           String dots = "...............................";  
           System.out.println(dots+dots);  
           while(currentSize > 0){  
                if(column == 0)  
                     for(int k=0; k<nBlanks; k++)  
                          System.out.print(' ');  
                System.out.print(heapArray[j].iData);  
                if(++j == currentSize)  
                     break;  
                if(++column==itemsPerRow){  
                     nBlanks /= 2;  
                     itemsPerRow *= 2;  
                     column = 0;  
                     System.out.println();  
                }else{  
                     for(int k=0; k<nBlanks*2-2; k++)  
                          System.out.print(' ');  
                }  
           }       
      }  
 }

HeapTest.java

 package com.nrs.ds.basic.queue.heap;  
 import java.io.BufferedReader;  
 import java.io.IOException;  
 import java.io.InputStreamReader;  
 public class HeapTest {  
      public static void main(String[] args) throws IOException {  
           int value, value2;  
           HeapImpl theHeap = new HeapImpl(31);  
           boolean success;  
           theHeap.insert(70);  
           theHeap.insert(40);  
           theHeap.insert(50);  
           theHeap.insert(20);  
           theHeap.insert(60);  
           theHeap.insert(100);  
           theHeap.insert(80);  
           theHeap.insert(30);  
           theHeap.insert(10);  
           theHeap.insert(90);  
           while(true){  
                putText(" \n Enter first letter of ");  
                putText("show, insert, remove, change: ");  
                int choice = getChar();  
                switch(choice){  
                case 's': // shows  
                     theHeap.displayHeap();  
                     break;  
                case 'i': // insert  
                     putText("Enter value to insert: ");  
                     value = getInt();  
                     success = theHeap.insert(value);  
                     if( !success )  
                     putText("Can't insert; heap is full" + '\n');  
                     break;  
                case 'r': // remove  
                     if( !theHeap.isEmpty() )  
                     theHeap.remove();  
                     else  
                     putText("Can't remove; heap is empty" +     '\n');  
                     break;  
                case 'c': // change  
                     putText("Enter index of item: ");  
                     value = getInt();  
                     putText("Enter new priority: ");  
                     value2 = getInt();  
                     success = theHeap.change(value, value2);  
                     if( !success )  
                     putText("Can't change; invalid index" +'\n');  
                     break;  
                default:  
                     putText("Invalid entry\n");  
                     }  
                }  
           }  
      private static int getChar() throws IOException {  
           String s = getString();  
           return s.charAt(0);  
      }  
      private static String getString() throws IOException {  
           InputStreamReader isr = new InputStreamReader(System.in);  
           BufferedReader br = new BufferedReader(isr);  
           String s = br.readLine();  
           return s;  
      }  
      private static int getInt() throws IOException {  
           String s = getString();  
           return Integer.parseInt(s);  
      }  
      private static void putText(String string) {  
           System.out.print(string);  
           System.out.flush();  
      }  
 }
Output:

Efficiency of Heap Operations : Heap operations we've talked about here all operate in O(logN) time.

Comments

Post a Comment

Popular posts from this blog

Tournament Tree or Winner Tree

Image
Tournament Tree or Winner Tree :  Is a form of min(max) heap which is a complete binary tree. every external node represents a player and internal node represents a winner. Winner: select the best player among N palyers , (N -1) players to be eliminated. we need minimum of (N-1) games (comparisons). Second best player: we can pick second best player in (N + log2(n-2)) comparisons.   The above tree contains 4 leaf nodes that represent players and have 3 levels 0, 1 and 2. Initially 2 games are conducted at level 2, one between 5 and 3 and another one between 7 and 8. In the next move, one more game is conducted between 5 and 8 to conclude the final winner. Overall we need 3 comparisons. For second best player we need to trace the candidates participated with final winner, that leads to 7 as second best. Uses: Tree selection sort using tournament tree.  
Read more

Linked List

Image
single linked list: 1. Node class NodeLL.java package com.nrs.ds.basic; public class NodeLL { Object value; NodeLL next; public NodeLL(Object value,NodeLL next){ this.value=value; this.next = next; } } 2. LinkedList implementation LinkedListImpl.java package com.nrs.ds.basic; public class LinkedListImpl<T> { NodeLL head; public LinkedListImpl(){ head = null; } public void add(Object value){ NodeLL newNode= new NodeLL(value,null); if(head == null){ head=newNode; }else{ newNode.next = head; head = newNode; } } public void delete(){ head = head.next; } public void display(){ NodeLL n=head; while(n != null){ System.out.println((T)n.value); n = n.next; } } ...
Read more

Heaps

Image
 A Binary Heap is either Min Heap or Max Heap. Min Binary Heap: the key at root must be minimum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Min Binary Heap: The key at root must be maximum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Binamial Heap: Binamial Heap  is a Extention of Binary Heap that provides faster union or merge operations together with other operations provided by Binary Heap. Is a collection of tinomial trees. Binamial Tree Tree: A binomial Tree of order 0 has 1 node. A binomial Tree oder k can be constructed by taking two binomial trees of order k-1, and making one as leftmost child of other.  Binomial Heap: Is a set of Binomial Tree where each Binomial Tree follows Min Heap Property. and there can be at-most one Binomial Tree of any degree. Fibonacci Heap:  In terms of Time Com...
Read more