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.

Comments

Popular posts from this blog

File upload problem: UTF-8 encoding not honored when form has multipart/form-data

The problem that I was facing was something like this. I was using Apache Commons File Upload library to upload and download some file.

I had a form in which user can upload a file and another field 'name' in which she can give any name to the file being loaded.


When I submitted the form, the file was uploaded fine but the value in name field was garbled. I followed all the possible suggestions I found:

<%@page pageEncoding="UTF-8"%> set. <%@page contentType="text/html;charset=UTF-8"%gt; set after the first directive. <meta equiv="Content-Type" content="text/html;charset=UTF-8"> in the head. enctype="multipart/form-data" attribute in the form. accept-charset="UTF-8" attribute in the form.
in the Servlet:
before doing any operations on request object: request.setCharacterEncoding("UTF-8"); For accessing the value

FileItem item = (FileItem) iter.next();

if (item.isFormField()) {

//For regular…

java.lang.IllegalArgumentException: Malformed \uxxxx encoding

I was getting this exception during build while running ant. Googling didn't help much and I was flummoxed because the same code was running fine till now.

My code reads a text file and does some operations on the basis of values read. It was only when I saw the text files I understood the error. I had copied the text in wordpad and saved it as .txt file. Wordpad had put lot of formatting information before and after the content. Also there was "\par" after every line, which was giving this error.

So moral of the story: if you get this exception check your properties file (or any other file that your code might be reading.)

Easiest way to print Timestamp in Java

Rather than using Calendar.getTime() we can use java.sql.Timestamp class to get the time stamp which gives date and time till millisecond precision.

System.out.println(new Timestamp(System.currentTimeMillis()));

Above will give you current timestamp in this format: 2010-07-27 16:37:45.39