Exploring Heap Data Structure In Java

Introduction

The article explains what Heap (Priority Queue) in Java is, its characteristics, understanding Min Heap / Max Heap, and explains a few important Java Priority Queue API methods. This article covers how to work with Comparator in Priority Queue. 

The article also explains the Time Complexity of every operation and at the end, it covers some important problems that can be solved using Priority Queue. In a nutshell, the article is a practical primer on Heap Data structure.

What is Priority Queue

Priority Queue or Heap is an important Data structure that is a queue, but it doesn’t store the elements in FIFO order, but it stores the elements based on Custom Comparator which is attached during Priority Queue creation. If no Custom Comparator is attached, then the elements are stored in Natural Order. 

• In Priority Queue sort order is not stable if two elements that are in the same position as per the comparator will not necessarily be removed in the same order as they were inserted. 
• Priority Queues are not bounded by the capacity meaning we cannot provide the size of the queue then it’s ideal to say these are unbounded queues. 
• Priority Queues does not allow "null" values. 
• Priority Queues are not thread-safe, the thread-safe version is PriorityBlockingQueue.  
• Priority Queue only works for "Comparable" Objects. 
• Priority Queue allows duplicate values.

Min Heap or Min Priority Queue

The Priority Queue can be called as Min Heap or Min Priority Queue when the ordering of elements is in ascending order and the smallest element is at the head of the queue. 

Max Heap or Max Priority Queue

Max Priority Queue is the reverse of Min, in Max Priority Queue the elements are in descending order and the greatest element is at the head of the queue. 

API Methods

The article covers 6 important methods from the Priority Queue object. 

1. add: The "add" method inserts an element to the Priority Queue. 
2. offer:  The "offer" method also does the same. It inserts the element to the Priority Queue. 
   Both methods perform the same operation with only 1 difference between the two, the add throws "IllegalStateException" if no space is available in the size restricted queue else it returns true. On the other hand, offer returns false in case no space is available. 
3. poll: The "poll" method returns and removes the head element of the Priority Queue. In case if the queue is empty, "poll" returns null. 
4. peek: The "peek" method returns the head element of the queue without deleting it. 
5. contains: The "contains" method checks whether the element exists in the queue, if the element exists it returns true. 
6. remove: The "remove" method returns and removes the head element of the Priority Queue. In case if the queue is empty, "remove" throws "NoSuchElementException". 

Time Complexity

• Time complexity of enqueuing/dequeuing elements from the Priority Queue is O (log n). 
  add, offer, poll, remove () – O (log n) 
  remove (Object o): removing a specific element from the Priority Queue has a time complexity of O (n). 
  But remember creating Priority Queue from the existing array the time complexity is O (n)  
• The Time complexity of "peek" operation is O (1) 
• The time complexity of "contains" is O (n) 

Priority Queue Examples

1. Store elements in ascending/descending order. 

public static void main(String[] args) {
    //Creating Empty Priority Queue
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    //add elements to the Priority Queue
    pq.offer(1);
    pq.offer(-4);
    pq.offer(2);
    //Remove and returns the elements from the PriorityQueue
    while(!pq.isEmpty()){
        System.out.println(pq.poll());
    }
}

In the given example we have not attached any custom comparator, in that case, elements are stored in natural order (ascending by default), and the result of the above operation is -4, 1, 2.

To store the elements in descending order we need to pass the custom comparator to the constructor. 

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

Now the output will be: 2, 1, -4

2. From the Strings in the Priority Queue find the String with max length. 

PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> Integer.compare(b.length(), a.length()));
pq.offer("New York");
pq.offer("Sydney");
pq.offer("NewPort Beach");

System.out.println(pq.poll()); // “NewPort Beach”

The comparator passed to Priority Queue is sorted in descending order of String length. 

Note: Problems that are doable using Priority Queue are those where we are asked to "find the highest / lowest K values". 

3. Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]

Solution

In this problem, if we can come up with a Comparator the solution from there is straight-forward and this statement stands valid for most of the problems that can be solved using Priority Queue. 

Since we are asked to find Euclidean distance the comparator may look something like 

PriorityQueue<int[]> pq = new PriorityQueue<int[]>((p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]);

Once this is done, then we only need to store the elements in the Priority Queue and find the result 

for (int[] point : points) {
    pq.offer(point);
    if (pq.size() > k) {
        pq.poll();
    }
}

Now iterate only till K and poll the elements.  

Conclusion

Priority Queue is an important Data structure in which elements are ordered in Natural Order for Custom Ordering we need to attach Comparator with Priority Queue.