Heaps / Priority Queue

In a heap, looking for an arbitrary element is O(n), thus removing an element is O(n) as well.

Use Two Heaps to Maintain Median Queries in O(1)

We can use two heaps (min & max heap) to maintain two sorted halves of a stream of numbers, so that we can have O(1) query of median. When we add num, we are not sure whether it is greater than or smaller than median, so add it to max heap first and then get the first element from max heap and add to min heap. If the num is smaller than median, it will be retrieved back and added to min heap.

class MedianFinder {
    private PriorityQueue<Integer> firstHalf; 
    private PriorityQueue<Integer> secondHalf;


    /** initialize your data structure here. */
    public MedianFinder() {
        firstHalf = new PriorityQueue<>((a,b)->b-a);
        secondHalf = new PriorityQueue<>((a,b)->a-b);
    }

    public void addNum(int num) {
        secondHalf.add(num);
        firstHalf.add(secondHalf.poll());
        if(firstHalf.size()>secondHalf.size()+1)
            secondHalf.add(firstHalf.poll());
    }

    public double findMedian() {
        if(firstHalf.size()>secondHalf.size())
            return firstHalf.peek();
        else
            return (firstHalf.peek() + secondHalf.peek()) /2.0;
    }
}

Use Heap to Select Top K Element

We can use a heap of size K to select top K elements. It is better than sorting the whole list and then get K elements (nlogn) because it only needs heap of size K and n inserts (nlogK).

*this comparison assumes the heap is normal implementation which takes nlogn to build.

List<String> result = new LinkedList<>();
for(Map.Entry<String, Integer> countEntry: countMap.entrySet()) {
    selectKPriQ.offer(countEntry);  //add anyway, and remove top one (which is the smallest) if size > k
    if(selectKPriQ.size()>k) 
        selectKPriQ.poll();
}

while(!selectKPriQ.isEmpty()) {
    result.add(0, selectKPriQ.poll().getKey()); //need to add to FIRST in the list!
}

return result;

Sometime, the ordering is more complicated, by freq and then by lexico order, we have to be careful with the pq comparator.

//For example, we want top k sent with increasing lexico ordering...
//k min heap of freq and 
//descending of string lexico order (so that we can always remove the top one from k-min heap)
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a,b) -> 
    a.getValue() == b.getValue()? b.getKey().compareTo(a.getKey()) : a.getValue() - b.getValue()
);

Use Heap to Maintain a Sorted Window

Interview Post

You are given an array of numbers and a positive integer k. You are allowed to move an element of the array at most k position earlier, or any number of positions later. Given this constraint, you need to make the array as sorted as possible.

For example, if k=2 and the input array is 5 4 2 3 1, then the output should be 2 3 1 4 5.

Solution: use a priority queue of size k+1, iterate over the list one by one, each time pop the smallest out. This essentially maintain the constraint that the smallest element will not be moved left more than k steps.

Use Heap to Select Next Smallest Number & Make Progress Through the LinkedList/Array

373. Find K Pairs with Smallest Sums

632. Smallest Range

It is common that we use priority queue to give us the next smallest/largest value, from the entry (coordinates, indexes, etc) that gives you the smallest/largest value, you can insert the next entry back into the pq. This will make progress and ensure the value given out from the pq is in proper order.

PriorityQueue<int[]> kMin = new PriorityQueue<>((a,b) ->a[0] - b[0]);
kMin.offer(new int[]{nums1[0]+nums2[0], 0, 0}); //[0] is the val, [1] is index1, [2] is index2