Priority Queue & Heap Sort
Priority Queue
Queue is an abstract data type that implements FIFO, first in first out.
Therefore when popping the element from a Queue, thre result will be always the oldest entry. Therefore, elements have to be inserted in the order of priority.
Priority queue, on the other hand, allows inserting prioritized elements in any order. Since insertion order doesn’t determine priority of an element, how priority is determined has to be defined.
Java Collection framework provides a class Java.util.Priority Queue. Elements can be prioritized using a comparator that is passed to the queue or it can be done based on natural ordering when no comparator is passed. Elements should be an object of a class that implements Comparable interface and define compareTo if natural ordering is used.
Below links are oracle documents regarding priority queue and comparable and comparator interface(java8). Comparator is a functional interface.
https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html
https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html
Priority queue’s insertion or removal can have better time complexity when it is implemented as an array-based heap (log(n)) rather than doubly linked list(n).
Let’s say an element with first priority is inserted last after inserting 10 elements before it.
When implemented as doubly linked list, it takes 10 times of comparison operations to get to the front of the queue. Doubly linked list has linearly linked elements one after another, so the element has to go through all the previous elements.
With array-based heap implementation, it takes log(10)=3 to get to the root, which is the height of the heap. Heap just needs to maintain heap propery of children being smaller or bigger than their parents.
Heap sort
sorting a heap can be done by extracting the minimum element n-times.If it takes log(n) to get the minimum element, then sorting takes nlog(n). Quick sort has worst time complexity of n², but that happens rarely. The average performance of quick sort is better than heap sort.
algorithm problems
Let’s look at some examples where heap sort can be applied.
Get J’s stories in your inbox
Join Medium for free to get updates from this writer.
Leetcode problem of merging k sorted list is one of the problems that can be easily solved using heap sort.
In the problem, each list is sorted in ascending order. The min element comes first and the max element comes last. Brute force solution of putting all the elements into a list and sorting doesn’t consider the fact that each list is already sorted. With heap(priority queue), it is possible to take advantage of each list already being sorted.
How ?:
The min element of each list is inserted into a min-heap (min-heap is determined by giving a proper comparator to the priority queue when constructing).
The smallest of the heap is extracted and added to a new list that will be returned. From the list where the extracted element originially came, take the next smallest element and put it into the heap.
It is guaranteed that each element inserted into the heap is the minimum of each list except the ones that are already added(already sorted) to the list that will be returned.
In other words, k-smallest elements out of all the rest elements of all k lists is always gathered in the heap. Therefore, extracting min from the heap and simply appending it to a new list will result in a sorted list.
insertion takes (logk) so time complexity for all the lists will be nlogk where n is the number of all the elements.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((node1, node2)-> node1.val - node2.val);for(ListNode list : lists){
if(list!=null)
pq.add(list);
}
ListNode dummyhead = new ListNode();
ListNode tail = dummyhead;
while(!pq.isEmpty()){
tail.next = pq.poll();
tail = tail.next;
if(tail.next!=null){
pq.add(tail.next);
}
}
return dummyhead.next;
}
}// When not using dummyhead, extra code when inserting the first element.
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((node1, node2)-> node1.val - node2.val);for(ListNode list : lists){
if(list!=null)
pq.add(list);
}
ListNode head = null;
ListNode tail = head;
while(!pq.isEmpty()){
ListNode node = new ListNode();
node= pq.poll();
if(head==null && tail==null){
head = node;
tail = node;}
else {
tail.next = node;
tail = node;
}
if(tail.next!=null){
pq.add(tail.next);
}
}
return head;
}
}The next problem is getting top K frequent elements.
Heap provides a good solution when computing k- largest or k-smallest elements (where n is total number of elements) .
Key point of this problem is that deeper heap means more swap operations for insertion. so the size of the heap has to be kept to given number k to get better time complexity of logk than logn (by discarding already sorted unnecessary part as soon as possible).
Let’s say the total number of elements is 9 with no duplicates. When k is 2, it is necessary to keep only top 2 elements, and time complexity for insertion of all elements when the heap has just 2 elements is 9log2. When inserting a new element to the heap, the new element will be compared maximum log2 times. (compared to only one element)
If the heap keeps all other elements, then the time complexity will increase to 9log9. When inserting a new element to the heap, the new element will be compared maximum log9 times.(compared to 3 elements in the worst case scenario.)
class Solution { //concise with lambda
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> hashmap = new HashMap<>();
for(int num:nums){ // default exists, so no need to use containsKey method
hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> pq = //using lambda makes code concise
new PriorityQueue<>((i1,i2)-> hashmap.get(i1) - hashmap.get(i2));
for(int num: hashmap.keySet()){
pq.add(num);
if(pq.size()>k){pq.poll();}// keep the size of heap small(to k)
}
int[] result = new int[k]; //lists all the elements in the heap
for(int i=0; i<k; i++){
result[i]=pq.poll();
}
return result;
}
}class Solution { // verbose version. no lambda
static int myComparator(Map.Entry<Integer,Integer> o1, Map.Entry<Integer,Integer> o2){
return (o2.getValue()- o1.getValue());
}
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> hashmap = new HashMap<>();
for(int num:nums){
if(hashmap.containsKey(num)){
hashmap.put(num, (hashmap.get(num))+1);
} else {
hashmap.put(num,1);
}
}
PriorityQueue<Map.Entry<Integer,Integer>> pq = new PriorityQueue<>(Solution::myComparator);
for(Map.Entry<Integer,Integer> entry: hashmap.entrySet()){
pq.add(entry);
}
int[] result = new int[k];
for(int i=0; i<k; i++){
result[i]=pq.poll().getKey();
}
return result;
}
}
