Algorithm of Priority Queue(Heap)

11/29/2021 algorithm

🟥🟧🟨 优先级队列的原理以及应用。🟩🟪🟫🟨

  1. 大根堆
  2. 小根堆(Python 默认)

# 大根堆与小根堆

# 大根堆

什么是大根堆?

# 小根堆

什么是小根堆?Python 默认是小根堆。

a = [1, 3, 2, -1, 0]
heapq.heapify(a)
heapq.heappop(a) # -1

# 优先级队列

# 原理与实现

🧡💛💚 在 Python 中,使用堆 (heapq) 来实现优先级队列。

  • 初始化时,直接将优先级队列初始化为列表: heap = [] ;
  • python 使用堆的时候,默认是小根堆

# LC786 第 K 个最小的素数分数

# 786. 第 K 个最小的素数分数 (opens new window)

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成,且其中所有整数互不相同。

对于每对满足 0 <i < j < arr.length 的 i 和 j ,可以得到分数 arr [i] /arr [j] 。

那么第 k 个最小的分数是多少呢?以长度为 2 的整数数组返回你的答案,这里 answer [0] == arr [i] 且 answer [1] == arr [j] 。

arr = [1,2,3,5], k = 3

输出:[2,5]

遇到第 k 大、第 k 小的问题,我们通常的思路就是使用优先级队列来实现。

该问题的实现代码如下所示:

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        heap = []

        # 默认小根堆
        n = len(arr)
        # 先把最小的那堆数入堆
        for i in range(1, n):
            heapq.heappush(heap, (arr[0] / arr[i], 0, i))
        i, j = 0, 0
        # why k
        for _ in range(k):
            val, i, j = heapq.heappop(heap)
            if i + 1 < j:
                heapq.heappush(heap, (arr[i + 1] / arr[j], i + 1, j))
        # why not heap
        return [arr[i], arr[j]]

这个代码实现中,有很多需要注意的细节:

  1. 记住 Python 默认的是小根堆;
  2. 我们在 for 循环中循环了 k 次,有时候我们会循环 k-1 次;这个细节需要留意,后续通过比较不同的题解对归类进行总结;
  3. 我们把最小的分数(分子为 1,分母为所有数构成的小根堆的堆顶元素)拿出来,然后将比这个元素大的元素放进堆(目的是为了比较放进堆的元素和原有堆中的元素的大小),而后按照顺序出堆,到第 k 个即为我们需要的元素。

# LC215 数组中的第 K 个最大元素

# 数组中的第 K 个最大元素 (opens new window)

给定整数数组 nums 和整数 k ,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

# 小根堆求解

这也是一个应用小根堆求解的问题,其实现代码如下:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = [x for x in nums[:k]]
        heapq.heapify(heap)
        for i in range(k, len(nums)):
            if nums[i] > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, nums[i])
        return heap[0]

从上段代码中我们可以看出:

  1. 在建立小根堆的时候,我们直接取了数组的前 k 个元素,用于建堆,如此一来我们可以从数组的剩余元素中一个一个添加元素,每增加一个元素,堆顶最小的元素就出堆了,直到我们将原数组中所有的元素都入堆了,最后留下了容量为 k 的小根堆,堆顶的元素就是第 k 大的元素;
  2. 需要注意,我们在是否出堆的时候有一个判断,即如果当前的元素比堆顶元素大,我们就把堆顶元素出推。

# 大根堆求解

除了这种小根堆的解法之外,我们也可以使用大根堆来求解这个问题,用大根堆求解的时候,我们只需要将堆 pop k 次,就可以得到第 k 大的元素。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = [-x for x in nums]
        heapq.heapify(heap)
        for _ in range(k - 1):
            heapq.heappop(heap)

        return -heap[0]

但是我们很容易看出,这种方法将整个数组都用于建堆了,其性能势必受到影响,在此是为了展示大根堆求解这个问题的方法。

# LC1439 有序矩阵中的第 k 个最小数组和

有序矩阵中的第 k 个最小数组和 (opens new window)

给你一个 m * n 的矩阵 mat,以及一个整数 k ,矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

输入:mat = [[1,3,11],[2,4,6]], k = 5

输出:7

解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:

[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。

# 暴力求解

对于这种题目,我们应当先掌握暴力求解的思路,再对其进行优化。

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        h = matrix[0][:]
        for row in matrix[1:]:
            h = sorted([i + j for i in row for j in h])[:k]
        return h[k - 1]

这个方法是可以 AC 的,我们现在分析一下为什么这个方法是可行的。

我们将所有的可能性全拿出来,然后取前 k 个,最后再拿出来我们想要的元素即可。

主要注意的是,我们每一次在生成 h 的时候,都只截取了前 K 个元素,这是因为后面的元素不再有竞争力(毕竟后面的肯定不是前 k 小的了),基于这个原则,我们每次都生成 k 个元素,最终把矩阵的每一行都遍历过去,得到我们想要的答案。

❓❓❓ why h = matrix[0][:] ?

比较疑惑,这里为什么要使用这个呢?仔细思考了一下,这段代码的目的是把矩阵的第一行元素复制下来,然后再和剩下的每一行元素加起来,这样会计算到所有的和吗?我们发现是可以的:🧡🧡 这个问题很巧妙的给出了一个答案:如何求解多个数组,每一个数组各取一个数字相加,所有可能的和?

举例来说,给定了数组如下:

matrix = [
    [1, 4, 7, 10],
    [2, 3, 5, 9],
    [1, 1, 12, 13]
]

我们要从这个数组的每一行元素中取一个元素,如从第一行中取 1 , 第二行中取 2 , 第三行中取 1 , 计算三者的和为 , 以此类推,我们计算出所有可能的和。

按照以前的思路,我们会将这三个数组的所有的排列组合计算出来,再求和,比如说使用 python 的 itertools.product :

def get_all_combines(self, mat: List[List[int]]):
    res = set()
    for nums in itertools.product(*mat):
        res.add(sum(nums))

    return list(res)

我们使用 set 来防止不必要的重复,先得到所有的组合,再对其进行求和,求和后添加到列表中保存,最终的结果为:

如果我们用上述的方法,可以写出如下代码很简单的求出:

def get_all_combines2(self, mat: List[List[int]]):
    h = mat[0][:]

    for nums in mat[1:]:
        h = sorted([i + j for i in h for j in nums])

    return list(set(h))

其实这种方法也没有避免了重复,但是可以不生成所有的组合可能性,极大减少了内存消耗,值得学习和细细品味!

# LC264 丑数 II

264. 丑数 II (opens new window)

给你一个整数 n ,请你找出并返回第 n丑数

丑数 就是只包含质因数 23 和 / 或 5 的正整数。

这道题目如何与优先级队列联系上呢?我们可以建立一个大小为 n 的堆,然后分别把符合要求的数入堆,最后那个堆顶元素就是我们想要的。我们需要保证堆的大小为 n, 我们初始化堆的初始为 [1] , 所以我们循环 n-1 次保证堆的大小,我们用大顶堆来最后取出堆顶元素即可。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        seen = {1}
        heap = [1]
        factors = (2, 3, 5)
        for _ in range(n - 1):
            cur = heapq.heappop(heap)
            for factor in factors:
                if (tmp := cur * factor) not in seen:
                    seen.add(tmp)
                    heapq.heappush(heap, tmp)
                    
        return heapq.heappop(heap)
更新时间: 2021年12月9日星期四 15:27