Earlier in we have seen Min-Heap and Max-Heap Implementation. Priority Queue is its built-in implementation in Java.
In this article we will see how to perform Min-Heap and Max-Heap using Priority Queue.
Brief:
A priority queue is an abstract data type where each element has a “priority” assigned to it. So the element with the higher priority is served before the other elements. Click here to know in detail about max-Heap and min-Heap. (Source : Wiki)
Return Type | Method | Description |
boolean | offer(E e) | Inserts the specified element into this priority queue. |
E | peek() | Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty. |
E | poll() | Retrieves and removes the head of this queue, or returns null if this queue is empty. |
int | size() | Returns the number of elements in this collection. |
void | clear() | Removes all of the elements from this priority queue. |
boolean | contains(Object o) | Returns true if this queue contains the specified element. |
Iterator<E> | iterator() | Returns an iterator over the elements in this queue. |
boolean | remove(Object o) | Removes a single instance of the specified element from this queue, if it is present. |
Comparator<? super E> | comparator() | Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements. |
Min-Heap using Priority Queue:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.PriorityQueue; | |
public class MinHeap_PQ { | |
PriorityQueue<Integer> pq; | |
public MinHeap_PQ() { | |
pq = new PriorityQueue<Integer>(); | |
} | |
public void insert(int[] x) { | |
for (int i = 0; i < x.length; i++) { | |
pq.offer(x[i]); | |
} | |
} | |
public int peek() { | |
return pq.peek(); | |
} | |
public int extractMin() { | |
return pq.poll(); | |
} | |
public int getSize() { | |
return pq.size(); | |
} | |
public void print() { | |
System.out.println(pq); | |
} | |
public static void main(String[] args) { | |
int[] arrA = { 1, 6, 2, 9, 4, 3, 8 }; | |
MinHeap_PQ i = new MinHeap_PQ(); | |
i.insert(arrA); | |
i.print(); | |
System.out.println("Min Element in the Priority Queue: " | |
+ i.extractMin()); | |
System.out.println("Min Element in the Priority Queue: " | |
+ i.extractMin()); | |
System.out.println("Min Element in the Priority Queue: " | |
+ i.extractMin()); | |
System.out.println("Priority Queue Size: " + i.getSize()); | |
} | |
} |
Output: [1, 4, 2, 9, 6, 3, 8] Min Element in the Priority Queue: 1 Min Element in the Priority Queue: 2 Min Element in the Priority Queue: 3 Priority Queue Size: 4
Max-Heap using Priority Queue:
This gets bit tricky here. By default the Priority Queue works as min-Heap. To implement the max-Heap we need to change the way priority queue works internally by overriding the Comparator.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Comparator; | |
import java.util.PriorityQueue; | |
public class MaxHeap_PQ { | |
PriorityQueue<Integer> pq; | |
public MaxHeap_PQ() { | |
pq = new PriorityQueue<Integer>(10, new Comparator<Integer>() { | |
@Override | |
public int compare(Integer o1, Integer o2) { | |
// TODO Auto-generated method stub | |
return o2 – o1; | |
} | |
}); | |
} | |
public void insert(int[] x) { | |
for (int i = 0; i < x.length; i++) { | |
pq.offer(x[i]); | |
} | |
} | |
public int extractMax() { | |
return pq.poll(); | |
} | |
public void display() { | |
System.out.println(pq); | |
} | |
public int getSize() { | |
return pq.size(); | |
} | |
public void print() { | |
System.out.println(pq); | |
} | |
public static void main(String[] args) { | |
int[] arrA = { 1, 6, 2, 9, 4, 3, 8 }; | |
MaxHeap_PQ i = new MaxHeap_PQ(); | |
i.insert(arrA); | |
i.print(); | |
System.out.println("Max Element in the Priority Queue: " | |
+ i.extractMax()); | |
System.out.println("Max Element in the Priority Queue: " | |
+ i.extractMax()); | |
System.out.println("Max Element in the Priority Queue: " | |
+ i.extractMax()); | |
System.out.println("Priority Queue Size: " + i.getSize()); | |
} | |
} |
Output: [9, 6, 8, 1, 4, 2, 3] Max Element in the Priority Queue: 9 Max Element in the Priority Queue: 8 Max Element in the Priority Queue: 6 Priority Queue Size: 4
Reference : https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html