目录

前言

各类操作

创建堆

向堆中添加元素

从堆中弹出最小的元素

查看堆中最小的元素

将一个列表转换成堆

使用最大堆

补充说明

相关算法题

题目

解题思路

解题代码

---

前言

堆是一种特别的完全二叉树结构，其中每个父节点的值都小于或等于其所有子节点的值（最小堆），或者每个父节点的值都大于或等于其所有子节点的值（最大堆）。

Python 的 heapq 模块提供了一种实现堆队列（也称为优先队列）的方式。（实现的为最小堆）

heapq 这个名字，它源自 "heap queue"，即“堆队列”。

各类操作

创建堆

在 heapq 中，堆是用列表来表示的。可以通过以下方式创建一个堆：

import heapq
heap = []

实际上，这同创建列表没有区别，创建的也只是一个普通的列表

heapq 模块通过对这个列表进行特定的操作，使其表现得像一个堆。重点在于，堆的属性（例如，父节点的值小于其子节点的值，这是最小堆的性质）并不是由列表本身的数据结构直接支持，而是由 heapq 模块提供的函数强加的规则。

向堆中添加元素

使用 heapq.heappush(heap, item) 向堆中添加元素，同时保持堆的属性。

heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)

从堆中弹出最小的元素

使用 heapq.heappop(heap) 从堆中移除并返回最小的元素，同时保持堆的属性。

smallest = heapq.heappop(heap)

查看堆中最小的元素

可以直接访问堆的第一个元素（heap[0]）来查看最小的元素，而不用弹出它。

smallest = heap[0]

将一个列表转换成堆

使用 heapq.heapify(x) 将列表 x 转换成堆，这个操作可以在 O(n) 时间内完成。

heapq.heapify(my_list)

使用最大堆

heapq 模块只提供了最小堆的实现。如果需要一个最大堆，一种简单的方法是将所有的值取负，这样最小的数在取负后就会变成最大的数。

# 添加元素到最大堆
heapq.heappush(max_heap, -item)

# 从最大堆获取最大元素
max_item = -heapq.heappop(max_heap)

补充说明

1. 在 Python 中，使用 heapq 操作的列表会被组织成一个堆结构，但这并不意味着列表中的元素会从左到右线性增大。实际上，堆是一种特殊的树形数据结构，具体来说是一个完全二叉树，它满足某个节点的值不大于（最小堆）或不小于（最大堆）其子节点的值，除了知道第一个元素是最小的，我们不能仅通过观察位置来直接确定列表中元素的排序。。
2. 在很多情况下，我们不需要队列的所有元素都完全有序。我们只需要能够快速访问和删除优先级最高的元素。基于堆的优先队列在这方面非常高效，特别是在插入和删除操作上。对于一个含有 n 个元素的堆，插入操作和删除最小元素的操作的时间复杂度都是 O(log n)。相比之下，如果维护一个始终完全有序的列表，插入操作可能需要 O(n) 的时间复杂度，因为可能需要移动列表中的多个元素来保持顺序。

相关算法题

题目

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

解题思路

对于此题，我们使用贪心算法加堆实现，尝试每一步都最大化利润

需要注意的是，zip（）函数实质上是把这两个列表（可迭代对象）一一对应打包成了元组

• 对于k次可选次数
• 当projects非空且其第一个元素的投资成本比我们当前总资本小或者相等
• 将这个项目的数据取出来，进行下一步操作，同时这个project也被从projects里pop出来了
• 把这个项目的利润变成负数，加入到我们的“最大堆”（因为此时我们是对利润取负的）
• 这样，我们就筛选出来了所有可以投资的堆
• 如果我们这些可以投资的堆非空，我们就投资最大荔韵的项目，并将利润加给当前的资本

解题代码

class Solution(object):
    def findMaximizedCapital(self, k, W, Profits, Capitals):
        current_capital = W
        projects = sorted(zip(Capitals, Profits), key=lambda x: x[0])
        max_heap = []

        for _ in range(k):
            while projects and projects[0][0] <= current_capital:
                capital, profit = heapq.heappop(projects)
                heapq.heappush(max_heap, (-profit, capital))
            
            if max_heap:
                current_capital += -heapq.heappop(max_heap)[0]
            else:
                break

        return current_capital