用Python刷LeetCode必备知识点1 - 优先级队列

用Python刷LeetCode必备知识点1 - 优先级队列

LeetCode里有很多道题都会用到一个数据结构叫优先级队列Priority Queue (min heap 或max heap)。优先级队列是用堆heap来实现的，最小值在队列顶部top的是最小堆（min heap），最大值在队列顶部的是最大堆（max heap）。

在python3，最小堆和最大堆是通过heapq模块和特殊函数__lt__()来实现的。heapq模块是用数组来实现堆的。对含有系统自带(build-in)的数据类型(int, float等)的数组list，可以用heapq成员函数heapify()直接把数组转换成成一个最小堆min heap。而对于用户自定义类型（如ListNode）的数组，则需要通过在自定义类型的类里重写__lt__()来实现最大堆或最小堆的。

最小堆或最大堆实现后，可以用heapq模块提供的两个函数实现压入和d出的 *** 作：heappush()和heappop()。

以下用两个实例来说明最小堆和最大堆的实现和应用：

最小堆，即永远是最小值在顶部的优先级队列：：

import heapq

class FreqWord:
    def __init__(self, w, f):
        self.freq = f
        self.word = w
    #最小堆，每次d出频率最小的单词
    def __lt__(self, other):
        return self.freq < other.freq

def main():
    word1 = FreqWord("i", 2)
    word2 = FreqWord("love", 3)
    word3 = FreqWord("leetcode", 4)
    word4 = FreqWord("coding", 5)

    pq = [word1, word2, word3, word4]
    heapq.heapify(pq)

    heapq.heappush(pq, FreqWord("2022", 1))

    while pq:
        word = heapq.heappop(pq)
        print(word.word, word.freq)

if __name__ == "__main__" :
    main()

最大堆，即永远是最大值在顶部的优先级队列：

import heapq

class FreqWord:
    def __init__(self, w, f):
        self.freq = f
        self.word = w
    #最大堆，每次d出频率最大的单词
    def __lt__(self, other):
        return self.freq < other.freq

def main():
    word1 = FreqWord("i", 2)
    word2 = FreqWord("love", 3)
    word3 = FreqWord("leetcode", 4)
    word4 = FreqWord("coding", 5)

    pq = [word1, word2, word3, word4]
    heapq.heapify(pq)

    heapq.heappush(pq, FreqWord("2022", 1))

    while pq:
        word = heapq.heappop(pq)
        print(word.word, word.freq)

if __name__ == "__main__" :
    main()

以下是LeetCode里用到优先级队列的两道题：

LeetCode 692. Top K Frequent Words - 前缀树（Trie Tree or Prefix Tree）系列题4https://blog.csdn.net/hgq522/article/details/121759977?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164072732216780261944187%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=164072732216780261944187&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-121759977.nonecase&utm_term=k+most&spm=1018.2226.3001.4450

LeetCode 23. Merge k Sorted Lists - 链表（linked List）系列题4 https://blog.csdn.net/hgq522/article/details/122228036