MaxHeap and MinHeap Implementations in Java

Sometimes a code-segment is worth a thousand words. Understanding the MaxHeap and MinHeaps using Java code is very easy. Here is an implementation of both.

MaxHeap :

package bst;

import java.util.ArrayList;

import java.util.List;

public class BinaryHeap {

   //ArrayList to hold the heap

    List h = new ArrayList();

   public BinaryHeap(){



   }

   //Constructs the heap - heapify

    public BinaryHeap(int[] e) {

       for(int i=0; i<e.length;i++)

       {

           add(e[i]);

       }

   }

   private int intGet(int key){

       return new Integer(h.get(key).toString()).intValue();

   }

   public void add(int key){

       h.add(null);

       int k = h.size()-1;

       while (k>0){

           int parent = (k-1)/2;

           int parentValue = new Integer(h.get(parent).toString()).intValue();

           //MaxHeap -

           //for minheap - if(key > parentValue)

            if(key <= parentValue){

               break;

           }

           h.set(k,parentValue);

           k=parent;

       }

       h.set(k,key);

   }

   public int getMax()

   {

       return new Integer(h.get(0).toString()).intValue();

   }

   public void percolateUp(int k, int key){

       if(h.isEmpty())

           return ;



       while(k < h.size() /2){

           int child = 2*k + 1; //left child

            if(child < h.size() -1 &&

              (new Integer(h.get(child).toString()).intValue() <

               new Integer(h.get(child+1).toString()).intValue()    )){

               child++;

           }

           if(key >= new Integer(h.get(child).toString()).intValue()){

               break;

           }

           h.set(k,new Integer(h.get(child).toString()).intValue());

           k=child;

       }

       h.set(k,key);

   }

   public int remove()

   {

       int removeNode = new Integer(h.get(0).toString()).intValue();

       int lastNode = new Integer(h.remove(h.size()-1).toString()).intValue();

       percolateUp(0,lastNode);

       return removeNode;

   }

   public boolean isEmpty()

   {

       return h.isEmpty();

   }



   public static void main(String[] args) {

       BinaryHeap heap = new BinaryHeap(new int[] {2,5,1});

       while(!heap.isEmpty()){

           System.out.println(heap.remove());

       }



   }

}

MinHeap :

package bst;

import java.util.*;



public class MinHeap<E extends Comparable<E>> {

 List<E> h = new ArrayList<E>();



 public MinHeap() {

 }



 public MinHeap(E[] keys) {

   for (E key : keys) {

     h.add(key);

   }

   for (int k = h.size() / 2 - 1; k >= 0; k--) {

     percolateDown(k, h.get(k));

   }

 }



 public void add(E node) {

   h.add(null);

   int k = h.size() - 1;

   while (k > 0) {

     int parent = (k - 1) / 2;

     E p = h.get(parent);

     if (node.compareTo(p) >= 0) {

       break;

     }

     h.set(k, p);

     k = parent;

   }

   h.set(k, node);

 }



 public E remove() {

   E removedNode = h.get(0);

   E lastNode = h.remove(h.size() - 1);

   percolateDown(0, lastNode);

   return removedNode;

 }



 public E min() {

   return h.get(0);

 }



 public boolean isEmpty() {

   return h.isEmpty();

 }



 void percolateDown(int k, E node) {

   if (h.isEmpty()) {

     return;

   }

   while (k < h.size() / 2) {

     int child = 2 * k + 1;

     if (child < h.size() - 1 && h.get(child).compareTo(h.get(child + 1)) > 0) {

       child++;

     }

     if (node.compareTo(h.get(child)) <= 0) {

       break;

     }

     h.set(k, h.get(child));

     k = child;

   }

   h.set(k, node);

 }



 // Usage example

  public static void main(String[] args) {

   MinHeap<Integer> heap = new MinHeap<Integer>(new Integer[] { 2, 5, 1, 3 });

   // print keys in sorted order

    while (!heap.isEmpty()) {

     System.out.println(heap.remove());

   }

 }

}