Min Heap and Max Heap Implementation in Java

Implement Heap data structure in Java.


 

We have already introduced heap data structure in previous post and covered heapify-up, push, heapify-down and pop operations. In this post, java implementation of Max Heap and Min heap is discussed.

 

1. Max Heap implementation in Java –

 

Below is java implementation of Max Heap data structure. We have tried to keep the implementation similar to Java.util.PriorityQueue Class.

Jump to Min Heap Implementation

Java

Download   Run Code


Output:


Priority Queue Size is 3
Priority Queue contains 2

Emptying queue: 15 3 2
Queue is Empty

Calling remove operation on an empty heap
java.lang.Exception: Index out of range(Heap underflow)
Element with highest priority is null

Calling peek operation on an empty heap
java.lang.Exception: Index out of range (Heap underflow)
Element with highest priority is null

Printing array: 45 4 5

Element with highest priority is 45
Element with highest priority is 5

 

2. Min Heap Implementation in Java –

 

The Min Heap Implementation in java is very similar to Max Heap Implementation discussed above. The highlighted portion in the below code marks its differences with max heap implementation.

Java

Download   Run Code


Output:


Priority Queue Size is 3
Priority Queue contains 2

Emptying queue: 2 3 15
Queue is Empty

Calling remove operation on an empty heap
java.lang.Exception: Index out of range(Heap underflow)
Element with highest priority is null

Calling peek operation on an empty heap
java.lang.Exception: Index out of range (Heap underflow)
Element with highest priority is null

Printing array: 4 5 45

Element with highest priority is 4
Element with highest priority is 5

 
The time complexity of add()/poll() operations is O(log(n)), toArray()/contains() is O(n) and peek()/size()/isEmpty() is O(1).

 

 
 
Exercise: Heap Implementation in Java using ArrayList instead of a Vector.

 
References: https://en.wikipedia.org/wiki/Heap_(data_structure)

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of