Java program to create a Binary Heap and Perform various operation

A binary heap (min-heap) is a complete binary tree with elements from a partially ordered set, such that the element at every node is less than (or equal to) the the element at it's left and right child.

This Binary Heap is a min-heap implemented with one-based array (root is element 1; children of element n are elements 2n and 2n+1) for simplicity.

Complexity: Space O(n), findMin O(1), insert O(logn), deleteMin O(logn), buildHeap O(n);

?

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

class BinaryHeap {    private int nodes[];  private int size;  private int capacity;       public BinaryHeap(int capacity) {   this.size = 0;   this.capacity = capacity;   this.nodes = new int[capacity + 1];  }    public int size() {   return size;  }    public int findMin() {   if (size <= 0) {    throw new RuntimeException("Empty Heap is empty.");   }   return nodes[1];  }    public void insert(int e) {   if (size >= capacity) {    throw new RuntimeException("Heap overflow.");   }     size++;   nodes[size] = e;   percolateUp();  }    public int deleteMin() {   if (size <= 0) {    throw new RuntimeException("Empty Heap is empty.");   }   int min = findMin();   nodes[1] = nodes[size];   size--;   percolateDown();   return min;  }    private void percolateDown() {   int index = 1;   while (true) {    int child = index * 2;    if (child > size)     break;    if (child + 1 <= size) {     // if there are two children -> take the smallest or     // if they are equal take the left one     child = findMin(child, child + 1);    }    if (nodes[index] <= nodes[child])     break;    swap(index, child);    index = child;   }  }    private void percolateUp() {   int index = size();   while (index > 1) {    int parent = index / 2;    if (nodes[index] >= nodes[parent])     break;    swap(index, parent);    index = parent;   }  }    private void swap(int i, int j) {   int temp = nodes[i];   nodes[i] = nodes[j];   nodes[j] = temp;  }    private int findMin(int leftChild, int rightChild) {   if (nodes[leftChild] <= nodes[rightChild]) {    return leftChild;   } else {    return rightChild;   }  }     public static void main(String[] args) {   BinaryHeap bh = new BinaryHeap(10);   bh.insert(7);   bh.insert(5);   bh.insert(9);   bh.insert(6);   bh.insert(4);   bh.insert(8);   bh.insert(10);   bh.insert(1);   bh.insert(3);   bh.insert(2);       System.out.println("Size of Binary Heap is : " + bh.size());     System.out.println("Delete min from Binary Heap : " + bh.deleteMin());   System.out.println("Size of Binary Heap is : " + bh.size());     System.out.println("Delete min from Binary Heap : " + bh.deleteMin());   System.out.println("Size of Binary Heap is : " + bh.size());  }    }

Output of this Program

Size of Binary Heap is : 10
Delete min from Binary Heap : 1
Size of Binary Heap is : 9
Delete min from Binary Heap : 2
Size of Binary Heap is : 8

Try this by Yourself : http://ideone.com/FnSiPv