[Leetcode] Heaps & Priority Queue

Introduction

Priority Queue
https://www.youtube.com/watch?v=t0Cq6tVNRBA&list=PLUL4IRMCZfeXjd5AzDyry39Mf_pn1YLjQ

Time Complexity

• Find min/max: O(1)
• Delete min/max: O(log(n))
• Insert: O(log(n))

Implementation
Python Queue: https://docs.python.org/3/library/queue.html#queue.PriorityQueue

from Queue import PriorityQueue

q = PriorityQueue()
q.put((1, item))
q.put((2, item2))
q.get() # remove and return

Python heapq: https://docs.python.org/2/library/heapq.html (use a priority queue to implemented a min heap)

from heapq import *

heap = [] # or list = [1,2,3], heap = heapify(list)
heappush(heap, item)
heappop(heap) # return min value
heappushpop(heap, item) # push item in the heap and then return the min value

347. Top K Frequent Elements

Leetcode: https://leetcode.com/problems/top-k-frequent-elements/description/

[Solution] Build a hashmap to record the frequency of numbers, and use MaxHeap to sort the elements in the HashMap

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // Construct a HashTale counting numbers
        Map<Integer, Integer> dict = constructHashMap(nums);

        // Use MaxHeap to keep sorted table
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(dict.size(),
            new Comparator<Map.Entry<Integer, Integer>>() {
                public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b) {
                    return b.getValue() - a.getValue();
                }
            }
        );

        // Insert items from hashmap to priority queue
        for (Map.Entry<Integer, Integer> entry: dict.entrySet()) {
            pq.offer(entry);
        }
        List<Integer> res = new ArrayList<Integer>();
        // get top k elements in pq
        for (int i = 0; i < k; i++) {
            Map.Entry<Integer, Integer> top = pq.poll();
            res.add(top.getKey());
        }
        return res;
    }

    private Map<Integer, Integer> constructHashMap(int[] nums) {
        Map<Integer, Integer> res = new HashMap<Integer, Integer>();
        for (int num: nums) {
            Integer cnt = res.get(num);
            if (cnt == null) {
                res.put(num, 1);
            } else {
                res.put(num, cnt + 1);
            }
        }
        return res;
    }
  }

692. Top K Frequent Words

[Solution] Same as above

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> dict = count(words);
        // Use heap sort
        PriorityQueue<Map.Entry<String,Integer>> pq = new PriorityQueue<>(dict.size(), new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> a, Map.Entry<String, Integer>b) {
                if (b.getValue() == a.getValue()) {
                    return a.getKey().compareTo(b.getKey());
                }
                return b.getValue() - a.getValue();
            }
        });

        // Insert entry into heap
        for (Map.Entry<String, Integer> entry: dict.entrySet()) {
            pq.offer(entry);
        }

        List<String> res = new ArrayList<String>();
        for (int i = 0; i < k; i++) {
            res.add(pq.poll().getKey());
        }
        return res;
    }

    private Map<String, Integer> count(String[] words) {
        if (words.length == 0) return null;
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            Integer ch = cnt.get(word);
            if (ch == null) {
                cnt.put(word, 1);
            } else {
                cnt.put(word, ch+1);
            }
        }
        return cnt;
    }
}

295. Find Median from Data Stream

[Solution]:

1. Use two heaps one min one max to store elements to the left of median and to the right of the median.

from heapq import *

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.small = [] # max heap (reversed min heap)
        self.big = [] # min heap
        

    def addNum(self, num: int) -> None:
        if len(self.small) == len(self.big):
            heappush(self.small, -heappushpop(self.big, -num))
        else:
            heappush(self.big, -heappushpop(self.small, -num))


    def findMedian(self) -> float:
        if len(self.small) == len(self.big):
            return (self.big[0] - self.small[0]) / 2
        else:
            return self.small[0]

Use heap to optimize sorting

23. Merge k Sorted Lists

Leetcode: https://leetcode.com/problems/merge-k-sorted-lists/

Time Complexity: O(nlogk), where k is the number of linked list.

from heapq import *

def mergeKLists(self, lists):
    head = ListNode(0)
    cur = head
    if not lists or len(lists) == 0:
        return head.next
    heap = []
    min_lst = lists[0]
    for lst in lists:
        if lst:
            heappush(heap, (lst.val, lst))
    while heap:
        val, node = heappop(heap)
        cur.next = ListNode(val)
        cur = cur.next
        node = node.next
        if node:
            heappush(heap, (node.val, node))
    return head.next

253. Meeting Rooms II

Leetcode: https://leetcode.com/problems/meeting-rooms-ii/

Solution: Use heap to optimize min function

from heapq import *

def minMeetingRooms(self, intervals):
    """
    :type intervals: List[List[int]]
    :rtype: int
    """
    intervals.sort(key = lambda x: x[0])
    if not intervals or len(intervals) == 0:
        return 0
    ends = []
    for interval in intervals:
        if ends and interval[0] >= ends[0]:
            heappushpop(ends, interval[1])
        else:
            heappush(ends, interval[1])
    return len(ends)