Top K Elements

heapq 的大型应用现场，常与 freq 配合使用。借助 index 可以实现对复杂 object 的比较，也可以通过 total_ordering 定义数据类。有时需要用队列暂存 heappop 的元素。

Any problem that asks us to find the Top K Elements among a given set falls under this pattern.

The best data structure that comes to mind to keep track of “K” elements is heap. This pattern will make use of the heap to solve multiple problems dealing with “K” elements at a time from a set of given elements.

Snippets

freq = dict()
for char in s:
    freq[char] = freq.get(char, 0) + 1

max_heap = []
for char in freq:
    heappush(max_heap, (-freq[char], char))

ans = ""
while max_heap:
    queue, k = [], 2  # store pop-up items
    while max_heap and k > 0:
        count, char = heappop(max_heap)
        ans += char

        if -count - 1 > 0:
            queue.append((count + 1, char))
        
        k -= 1
    
    if k > 0 and queue:
        return ""
    
    for item in queue:
        heappush(max_heap, item)  # push back

return ans

LeetCode

692. Top K Frequent Words
215. Kth Largest Element in an Array
973. K Closest Points to Origin
1167. Minimum Cost to Connect Sticks
347. Top K Frequent Elements
451. Sort Characters By Frequency
703. Kth Largest Element in a Stream
658. Find K Closest Elements
1481. Least Number of Unique Integers after K Removals
1508. Range Sum of Sorted Subarray Sums
767. Reorganize String
358. Rearrange String k Distance Apart
621. Task Scheduler
895. Maximum Frequency Stack