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

Similar Programs Chapter Last Updated
HashMap Implementation In Java Data Structures 07-07-2018
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 22-09-2018
Stack Implementation In Java Data Structures 22-09-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Infix Expression To Postfix Expression Data Structures 25-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 26-09-2018
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016

1 2 3