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 to upload to Google Cloud Storage buckets using CURL

Signed URLs are pretty nifty feature given by Google Cloud Platform to let anyone access your cloud storage (bucket or any file in the bucket) without need to sign in. Official documentation gives step by step details as to how to read/write to the bucket using gsutil or through a program. This article will tell you how to upload a file to the bucket using curl so that any client which doesn't have cloud SDK installed can do this using a simple script. This command creates a signed PUT URL for your bucket. gsutil signurl -c 'text/plain' -m PUT serviceAccount.json gs://test_bucket_location Here is my URL: https://storage.googleapis.com/test_sl?GoogleAccessId=my-project-id@appspot.gserviceaccount.com&Expires=1490266627&Signature=UfKBNHWtjLKSBEcUQUKDeQtSQV6YCleE9hGG%2BCxVEjDOmkDxwkC%2BPtEg63pjDBHyKhVOnhspP1%2FAVSr%2B%2Fty8Ps7MSQ0lM2YHkbPeqjTiUcAfsbdcuXUMbe3p8FysRUFMe2dSikehBJWtbYtjb%2BNCw3L09c7fLFyAoJafIcnoIz7iJGP%2Br6gAUkSnZXgbVjr6wjN%2FIaudXIqA...
Post a Comment
Read more

Running Apache Beam pipeline using Spark Runner on a local standalone Spark Cluster

The best thing about Apache Beam ( B atch + Str eam ) is that multiple runners can be plugged in and same pipeline can be run using Spark, Flink or Google Cloud Dataflow. If you are a beginner like me and want to run a simple pipeline using Spark Runner then whole setup may be tad daunting. Start with Beam's WordCount examples  which help you quickstart with running pipelines using different types of runners. There are code snippets for running the same pipeline using different types of runners but here the code is running on your local system using Spark libraries which is good for testing and debugging pipeline. If you want to run the pipeline on a Spark cluster you need to do a little more work! Let's start by setting up a simple standalone single-node cluster on our local machine. Extending the cluster is as easy as running a command on another machine, which you want to add to cluster. Start with the obvious: install spark on your machine! (Remember to have Java a...
Post a Comment
Read more

Example of Using SimpleHttpOperator to make POST call

Airflow has SimpleHttpOperator which can be used to invoke REST APIs. However using this operator is not exactly straightforward. Airflow needs to be told about the connection parameters and all the other information that is needed to connect to external system. For this we need to create Connections. Open 'Connections' page through Admin->Connections link.  Expand the dropdown to see the various types of connection options available. For a REST call, create an HTTP connection. Give the host URL and any other details if required. Now when we write our task using SimpleHttpOperator we will need to refer to the connection that was just created. The task below is making a post call to  https://reqres.in/api/users  API and passing it some data in JSON format. myHttpTask = SimpleHttpOperator(  task_id='get_op',  method='POST',  http_conn_id='dcro',  data=json.dumps({    "name":"Morpheus",    " job ":" L...
Post a Comment
Read more