Skip to main content

Java implementation of Binary Heap (source code)

Binary Heaps are one of the easiest and most popular means to implement priority queues. You can get a lot of tutorials explaining the algorithms for insertion, deletion of the maximum (or minimum) element and using the heap for implementing priority queue.

Here is a simple Java code for these:



  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import java.util.Arrays;

class BinaryHeapImpl {  
  private int arr[];
  private int heapSize = 0;
  
  BinaryHeapImpl(int size){
    arr = new int[size];
    //initialize the array with -1
    Arrays.fill(arr, -1);    
  }
  
  private int getParentIndex(int index){
    System.out.println("finding parent of index "+index);
    if(index == 0)
      return 0;
    return (index%2 == 0)?((index/2) - 1):index/2;
  }
  
  public void insert(int element){
    arr[heapSize] = element;
    //when any element comes compare it with its parent whose index is k/2    
    int parentIndex = getParentIndex(heapSize);
    int parent = arr[parentIndex];
    if(element > parent){
      swim(heapSize, parentIndex);
    }
    heapSize++;
  }
  
  private void swim(int index, int indexParent){
    System.out.println("Swim :"+ arr[index]+"("+index+")" +" parent " + arr[indexParent] +"("+indexParent+")");
    if(indexParent >= 0){
      if(arr[index] > arr[indexParent]){
        exchange(index, indexParent);
        System.out.println("After exchange " +arr[index] +"  "+arr[indexParent]);
        if(indexParent!=0){
          swim(indexParent, getParentIndex(indexParent)); 
        }
      }
    }
  }
  
  private void sink(int index){
    System.out.println("Sinking "+arr[index]+"("+index+")");
    if(2*index+2 < heapSize){
      if(arr[index] < arr[2*index+1] || arr[index] < arr[2*index+2]){
        
        //replace the lower element with the bigger of its children. 
        int changeIndex = (arr[2*index+1] > arr[2*index+2])? 2*index+1 : 2*index+2;
        exchange(index, changeIndex);
        sink(changeIndex);
      }
    }
  }
  
  private void exchange(int index1, int index2){
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
  }
  
  public int getHeapSize(){
    return heapSize;
  }
  
  public void showHeap(){
    System.out.print("\nShowing heap:");
    for(int i = 0; i< heapSize; i++){
      System.out.print(arr[i]+"  ");
    }
  }
  
  public int delMax(){
   //replace top with last.
    int max = arr[0]; //this is to be returned
    int lastIndex = heapSize - 1;
    int last = arr[lastIndex];
    arr[lastIndex] = -1;
    
    //Move the last element to top and then sink it down
    arr[0] = last;
    sink(0);
    
    //reduce the heapSize
    heapSize--;
    return max;
  } 
  
}

public class BinaryHeap{
   
  public static void main(String args[]){
   int arr[];
   int size = 10;  
    arr = new int[size];
  
    //Create tree.
    BinaryHeapImpl bh = new BinaryHeapImpl(10);
    bh.insert(5);
    bh.showHeap();
    bh.insert(4);
    bh.showHeap();
    bh.insert(3);
    bh.showHeap();
    bh.insert(6);
    bh.showHeap();
    bh.insert(2);
    bh.showHeap();
    bh.insert(7);
    bh.showHeap();
    bh.insert(8);
    bh.showHeap();
    bh.insert(1);
    bh.showHeap();
    bh.insert(9);
    bh.showHeap();
    //bh.insert(0);
    System.out.println("Current Heapsize = "+bh.getHeapSize());
    
    System.out.println(bh.delMax());
    bh.showHeap();
    System.out.println(bh.delMax());
    bh.showHeap();
    System.out.println(bh.delMax());
    bh.showHeap();
    System.out.println(bh.delMax());
    bh.showHeap();
    System.out.println(bh.delMax());
    bh.showHeap();
  }
  
  
}

Post in comments if you need any clarification of this code.
Labels:

Comments

Post a Comment

Popular posts from this blog

How I converted a table in an email to a graph on a website? Hint: Azure Functions and Logic App

This mini-project started as a necessity.  I get an email like this everyday, which gives daily numbers for different metrics. The problem with such an email is that it is difficult to keep track of or gauge the rate of growth of these metrics. If you want to know how what the previous day's numbers were you need to go to the previous day's email.  The better option any day is to have a graph that shows the values of the metrics every day. Something like this: With this goal I set out to make this system but with as less coding and expenses as possible.  First obvious step in the process was to get hold of the email and extract its text. The easiest way to do this is to use Azure Logic App.  Here is what my logic app looks like: When any new email arrives in my Outlook 365 account, with a subject that contains "System usage Stats as on", it passes the body of the email to an Azure function named 'EmailTextCleanerFunction' (code below), whose job is to clean an...
Post a Comment
Read more

Changing Eclipse Workspace Directory

Recently I moved my entire Eclipse installation directory but the workspace was still getting created in the older location only. And worst there was no option to select the Workspace directory in the Window->Options->Workspace menu. To change the workspace location in Eclipse do this. Goto ECLIPSE_HOME\configuration\.settings directory, edit the org.eclipse.ui.ide.prefs file and change the RECENT_WORKSPACES value to the desired location. If you want that Eclipse prompts you to select workspace when you start it, change the SHOW_WORKSPACE_SELECTION_DIALOG value to true. And you are done!
10 comments
Read more

Hands on review: Yahoo! Mail app for Windows 8

Before you start mocking me for using Yahoo! Mail, let me explain that this is NOT my primary mail account and I use Gmail and Outlook.com for my daily use. Yes, this Yahoo! account was once my daily haunt but that was during college days and those days are long gone. I don't use Yahoo! Mail much but still there are some group subscriptions and I just log in once in a while to see what's happening in those forgotten groups. And due to this reason, I have always kept track of changes in Yahoo! Mail and the fact is that you can blame them for everything but not really lack of trying. Though most of those tries just ended up cluttering the UI and adding somewhat needless features. However, now we hear that new CEO Marissa Mayer is focusing once again on the mail and first major product to come out is Yahoo! Mail app for Windows 8. So how is it? The Login screen is pretty neat and purple background with an envelope watermark is very pleasing, very Yahoo!. However why ...
7 comments
Read more