Java Program To Implement Heap

Chapter: Data Structures Last Updated: 12-07-2016 14:51:42 UTC

Program:

            /* ............... START ............... */
                
import java.util.Scanner;

class Heap {

	private int[] heapArray;
	private int maxSize;
	private int heapSize;

	public Heap(int mx) {
		maxSize = mx;
		heapSize = 0;
		heapArray = new int[maxSize];
	}

	public boolean isEmpty() {
		return heapSize == 0;
	}

	public boolean insert(int ele) {
		if (heapSize + 1 == maxSize)
			return false;
		heapArray[++heapSize] = ele;
		int pos = heapSize;
		while (pos != 1 && ele > heapArray[pos / 2]) {
			heapArray[pos] = heapArray[pos / 2];
			pos /= 2;
		}
		heapArray[pos] = ele;
		return true;
	}
	
	public int remove() {
		int parent, child;
		int item, temp;
		if (isEmpty())
			throw new RuntimeException("Error : Heap empty!");

		item = heapArray[1];
		temp = heapArray[heapSize--];

		parent = 1;
		child = 2;
		while (child <= heapSize) {
			if (child < heapSize && heapArray[child] < heapArray[child + 1])
				child++;
			if (temp >= heapArray[child])
				break;

			heapArray[parent] = heapArray[child];
			parent = child;
			child *= 2;
		}
		heapArray[parent] = temp;

		return item;
	}

	public void displayHeap() {
		/* Array format */
		System.out.print("\nHeap array: ");
		for (int i = 1; i <= heapSize; i++)
			System.out.print(heapArray[i] + " ");
		System.out.println("\n");
	}
}

public class JavaHeapImplementaion {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println("Heap Test\n\n");
		System.out.println("Enter size of heap");
		Heap h = new Heap(scanner.nextInt());

		char ch;
		
		do {
			System.out.println("\nHeap Operations\n");
			System.out.println("1. insert ");
			System.out.println("2. delete item with max key ");
			System.out.println("3. check empty");

			boolean chk;
			int choice = scanner.nextInt();
			switch (choice) {
			case 1:
				System.out.println("Enter integer element to insert");
				chk = h.insert(scanner.nextInt());
				if (chk)
					System.out.println("Insertion successful\n");
				else
					System.out.println("Insertion failed\n");
				break;
			case 2:
				System.out.println("Enter integer element to delete");
				if (!h.isEmpty())
					h.remove();
				else
					System.out.println("Error. Heap is empty\n");
				break;
			case 3:
				System.out.println("Empty status = " + h.isEmpty());
				break;
			default:
				System.out.println("Wrong Entry \n ");
				break;
			}
			h.displayHeap();

			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

Heap Test


Enter size of heap

3

Heap Operations

1. insert 
2. delete item with max key 
3. check empty
1
Enter integer element to insert
4
Insertion successful


Heap array: 4 


Do you want to continue (Type y or n) 

y

Heap Operations

1. insert 
2. delete item with max key 
3. check empty
3
Empty status = false

Heap array: 4 


Do you want to continue (Type y or n) 

n

Notes:

  • A heap is a specialized tree-based data structure that satisfies the heap property.
  • Heaps are crucial in several efficient graph algorithms such as Dijkstra’s algorithm and in the sorting algorithm heapsort.

Tags

Implement 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