leetcode Heap/Queue

3066. 超过阈值的最少操作数 II

输入：nums = [2,11,10,1,3], k = 10
输出：2
解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。
第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。

class Solution:def minOperations(self, nums: List[int], k: int) -> int:res = 0h = nums[:]heapify(h)while h[0] < k:x = heappop(h)y = heappop(h)heappush(h, x + x + y)res += 1return res

• 首先想到排序才能获得最小值，但如果每次更新都排序或2分搜索，巨慢，所以直接使用heap priority Q
• 这里面有两个点要注意：
  • heappush 和 heappop
  • 以及，用"加法"替换了"乘法"

Heap Vs. Priority Queue

Heap 直接对底层进行操作，相当快和轻量

import heapq
h = [10, 5, 20]
heapq.heapify(h) #这就是如何将已有list转化为heap

Priority queue在工程项目里更多用到，主要原因还是多线程的安全
以下是等效的例子：

它们最终都会输出：
处理任务: 打电话 (优先级: 1)
处理任务: 写邮件 (优先级: 2)
处理任务: 开会 (优先级: 3)

import heapqtasks = [(2, '写邮件'), (1, '打电话'), (3, '开会')]  # 优先级, 任务
heapq.heapify(tasks)while tasks:priority, task = heapq.heappop(tasks)print(f'处理任务: {task} (优先级: {priority})')

from queue import PriorityQueuetasks = PriorityQueue()
tasks.put((2, '写邮件'))
tasks.put((1, '打电话'))
tasks.put((3, '开会'))while not tasks.empty():priority, task = tasks.get()print(f'处理任务: {task} (优先级: {priority})')