Java Program To Implement Binary Heap
Chapter:
Data Structures
Last Updated:
12-07-2016 15:10:09 UTC
Program:
/* ............... START ............... */
import java.util.Scanner;
import java.util.Arrays;
import java.util.NoSuchElementException;
class BinaryHeap {
private static final int d = 2;
private int heapSize;
private int[] heap;
public BinaryHeap(int capacity) {
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
public boolean isEmpty() {
return heapSize == 0;
}
public boolean isFull() {
return heapSize == heap.length;
}
public void makeEmpty() {
heapSize = 0;
}
private int parent(int i) {
return (i - 1) / d;
}
private int kthChild(int i, int k) {
return d * i + k;
}
public void insert(int x) {
if (isFull())
throw new NoSuchElementException("Overflow Exception");
/** Percolate up **/
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
public int findMin() {
if (isEmpty())
throw new NoSuchElementException("Underflow Exception");
return heap[0];
}
public int deleteMin() {
int keyItem = heap[0];
delete(0);
return keyItem;
}
public int delete(int ind) {
if (isEmpty())
throw new NoSuchElementException("Underflow Exception");
int keyItem = heap[ind];
heap[ind] = heap[heapSize - 1];
heapSize--;
heapifyDown(ind);
return keyItem;
}
private void heapifyUp(int childInd) {
int tmp = heap[childInd];
while (childInd > 0 && tmp < heap[parent(childInd)]) {
heap[childInd] = heap[parent(childInd)];
childInd = parent(childInd);
}
heap[childInd] = tmp;
}
private void heapifyDown(int ind) {
int child;
int tmp = heap[ind];
while (kthChild(ind, 1) < heapSize) {
child = minChild(ind);
if (heap[child] < tmp)
heap[ind] = heap[child];
else
break;
ind = child;
}
heap[ind] = tmp;
}
private int minChild(int ind) {
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < heapSize)) {
if (heap[pos] < heap[bestChild])
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
public void printHeap() {
System.out.print("\nHeap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] + " ");
System.out.println();
}
}
public class JavaBinaryHeapExample {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Binary Heap Test\n\n");
System.out.println("Enter size of Binary heap");
BinaryHeap bh = new BinaryHeap(scanner.nextInt());
char ch;
do {
System.out.println("\nBinary Heap Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete min");
System.out.println("3. check full");
System.out.println("4. check empty");
System.out.println("5. clear");
int choice = scanner.nextInt();
switch (choice) {
case 1:
try {
System.out.println("Enter integer element to insert");
bh.insert(scanner.nextInt());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 2:
try {
System.out.println("Min Element : " + bh.deleteMin());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 3:
System.out.println("Full status = " + bh.isFull());
break;
case 4:
System.out.println("Empty status = " + bh.isEmpty());
break;
case 5:
bh.makeEmpty();
System.out.println("Heap Cleared\n");
break;
default:
System.out.println("Wrong Entry \n ");
break;
}
bh.printHeap();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scanner.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
}
}
/* ............... END ............... */
Output
Binary Heap Test
Enter size of Binary heap
3
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
4
Empty status = true
Heap =
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
4
Heap = 4
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
2
Heap = 2 4
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
3
Full status = false
Heap = 2 4
Do you want to continue (Type y or n)
n
Notes:
-
A binary heap is a heap data structure created using a binary tree.
- Heaps are crucial in several efficient graph algorithms such as Dijkstra’s algorithm and in the sorting algorithm heapsort.
Tags
Implement Binary Heap, Java, Data Structure