堆 (优先队列)

定义

堆是一种特殊的完全二叉树，其中每个节点的键值都满足某种顺序属性：

• 大顶堆（Max Heap）：对于任意节点i（除了根节点），其值都大于或等于其子节点的值。换句话说，每个父节点的值都大于或等于其子节点的值。
• 小顶堆（Min Heap）：对于任意节点i（除了根节点），其值都小于或等于其子节点的值。换句话说，每个父节点的值都小于或等于其子节点的值。

堆通常用数组来实现，因为数组可以高效地通过索引访问节点，而不需要存储指向父节点或子节点的指针。在数组实现中，对于任意节点i（数组索引从0开始）：

• 其左子节点的索引是 2*i + 1
• 其右子节点的索引是 2*i + 2
• 其父节点的索引是 (i-1)/2（向下取整）

堆支持的主要操作包括插入（将新元素添加到堆中并重新调整以保持堆的性质）、删除（移除根节点并重新调整堆）以及查找最大（或最小）元素（在大顶堆或小顶堆中，根节点总是最大或最小的）。

计算机数据结构中的“堆”和计算机内存管理中的“堆”是两个不同的概念：

1. 数据结构中的堆（Heap）：

• 这是一种特殊的树形数据结构，通常用于实现优先队列。在堆中，任意节点的值总是不大于（或不小于）其子节点的值（大顶堆或小顶堆）。
• 堆可以非常高效地支持两种主要操作：插入元素和提取最大（或最小）元素。
• 堆通常有两种实现方式：数组和链表。在数组实现中，堆可以通过数组索引关系快速定位父节点和子节点。

2. 内存管理中的堆（Memory Heap）：

• 这是操作系统用来动态分配内存的区域。程序可以在运行时请求一定量的内存，并在使用完毕后释放。
• 堆内存不是预先分配的，而是根据需要动态分配的。这与栈内存不同，栈内存是在程序运行前就已经分配好的。
• 堆内存管理涉及到复杂的算法，如内存分配器（如ptmalloc, jemalloc等）和垃圾回收机制（在某些语言中，如Java和C#）。

基本操作&实现

def heappush(heap, item):"""Push item onto heap, maintaining the heap invariant."""heap.append(item)_siftdown(heap, 0, len(heap)-1)def heappop(heap):"""Pop the smallest item off the heap, maintaining the heap invariant."""lastelt = heap.pop()    # raises appropriate IndexError if heap is emptyif heap:returnitem = heap[0]heap[0] = lastelt_siftup(heap, 0)return returnitemreturn lasteltdef heapify(x):"""Transform list into a heap, in-place, in O(len(x)) time."""n = len(x)# Transform bottom-up.  The largest index there's any point to looking at# is the largest with a child index in-range, so must have 2*i + 1 < n,# or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so# j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is# (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.for i in reversed(range(n//2)):_siftup(x, i)def _siftdown(heap, startpos, pos):newitem = heap[pos]# Follow the path to the root, moving parents down until finding a place# newitem fits.while pos > startpos:parentpos = (pos - 1) >> 1parent = heap[parentpos]if newitem < parent:heap[pos] = parentpos = parentposcontinuebreakheap[pos] = newitemdef _siftup(heap, pos):endpos = len(heap)startpos = posnewitem = heap[pos]# Bubble up the smaller child until hitting a leaf.childpos = 2*pos + 1    # leftmost child positionwhile childpos < endpos:# Set childpos to index of smaller child.rightpos = childpos + 1if rightpos < endpos and not heap[childpos] < heap[rightpos]:childpos = rightpos# Move the smaller child up.heap[pos] = heap[childpos]pos = childposchildpos = 2*pos + 1# The leaf at pos is empty now.  Put newitem there, and bubble it up# to its final resting place (by sifting its parents down).heap[pos] = newitem_siftdown(heap, startpos, pos)

python中对应的库

Python 的 heapq 模块提供了一个基于列表的堆队列算法的实现，也称为优先队列。以下是 heapq 模块的一些常用方法和注意事项：

常用方法：

1. heappush(heap, item)：

   • 将元素 item 添加到堆 heap 中。
   • 堆是递增的，即父节点总是小于或等于其子节点（小顶堆）。

2. heappop(heap)：

   • 移除并返回堆 heap 中的最小元素。
   • 这个操作保持了堆的性质。

3. heapify(x)：

   • 将列表 x 转换成堆。
   • 转换后的列表将满足堆的性质，即父节点小于子节点。

4. heapreplace(heap, item)：

   • 移除堆 heap 中的最小元素，并返回它，然后添加 item 到堆中。
   • 这个方法在保持堆的性质的同时，实现了元素的替换。

5. nlargest(n, iterable, key=None)：

   • 返回 iterable 中的 n 个最大元素。
   • 可以指定 key 函数来确定元素的比较方式。

6. nsmallest(n, iterable, key=None)：

   • 返回 iterable 中的 n 个最小元素。
   • 可以指定 key 函数来确定元素的比较方式。

注意事项：

1. 堆的性质：

   • 默认情况下，heapq 实现的是小顶堆，即父节点的值小于子节点的值。
   • 要实现大顶堆，可以在添加和移除元素时对元素的值取负。

2. 列表作为堆：

   • heapq 使用列表来实现堆，因此列表的索引可以用来定位父节点和子节点。
   • 父节点 i 的左子节点索引是 2*i + 1，右子节点索引是 2*i + 2，父节点索引是 (i-1)//2。

3. 效率：

   • heappush 和 heappop 操作的时间复杂度是 O(log n)。
   • heapify 操作的时间复杂度是 O(n)，适用于将一个列表转换为堆。

4. 稳定性：

   • heapq 不保证元素的顺序，即使元素具有相同的值，它们在堆中的顺序也可能不同。

5. 内存使用：

   • 由于 heapq 使用列表实现，大量元素可能会占用较多的内存。

6. 线程安全：

   • heapq 操作不是线程安全的，如果需要在多线程环境中使用，需要外部同步。

7. 错误处理：

   • 如果尝试从空堆中弹出元素，heapq 会抛出 IndexError。
   • 如果尝试在空堆上执行 heappop 或 heapreplace，应该先检查堆是否为空。

8. Python版本：
   从Python 3开始，heapq模块的函数（包括heappush、heappop和heapify）都支持一个key参数，允许你指定一个函数，该函数会被用来从列表中的每个元素中提取一个用于比较的键。这个键用于确定元素在堆中的顺序。

下面是一个使用key参数来指定排序键的例子：

import heapq# 假设我们有一个列表，其中包含一些元组，我们想根据元组的第二个元素来建立堆
data = [(1, 'apple'), (3, 'pear'), (2, 'orange'), (5, 'banana'), (4, 'grape')]# 使用heapq.heapify将列表转换为堆，并指定排序键为元组的第二个元素
heapq.heapify(data, key=lambda x: x[1])# 现在，我们可以使用heapq.heappop来获取最小元素
print(heapq.heappop(data))  # 输出: (3, 'pear')，因为'pear'是所有水果中字典序最小的

常见题型

215数组中第k大元素

法一 暴力解法

对于所有元素排序后返回对应位置的值
时间复杂度O(nlogn),空间复杂度O(logn)

法二 使用堆 （注意如果要手写堆如何实现 todo）

对于每个元素取负之后用heapq中函数构建堆，并弹出k次最小元素，最后一次的结果的负数就是解

import heapq
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:t = [-n for n in nums]heapq.heapify(t)ans = 0 for _ in range(k):ans = heapq.heappop(t)return -ans

时间复杂度：O(nlogn)，建堆的时间代价是 O(n)，删除的总代价是 O(klogn)，因为 k<n，故渐进时间复杂为 O(n+klogn)=O(nlogn)。

空间复杂度：O(logn)，即递归使用栈空间的空间代价。

法三 基于快速排序的选择算法

快排过程时每次选择一个基准，然后将所有比基准小的放在基准前，所有大于等于基准的放在基准后面，然后对于左右子序列重复这个过程直到左右子序列都是空，最终的序列就是有序的

对于本题，媒体确定基准排序后的位置，和第k大的数排序后的位置对比，确定直接返回还是继续对于左或右重复刚才的操作，从而可以减少每次遍历的范围。

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:length = len(nums)target = length - k def partition(j, left, right):cur = leftfor i in range(left, right):if nums[i]<nums[j]:nums[i], nums[cur] = nums[cur], nums[i]cur += 1nums[cur], nums[j] = nums[j], nums[cur]return cur left, right = 0, length-1n = rightwhile True:t = partition(n, left, right)if t==target:return nums[target]elif t<target:left = t+1n = rightelse:right = t-1n = right

上面的代码在有大量重复1的测试用例中无法通过。

题解

改进后的解法

import random
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def partition(nums, left, right):rn = random.randint(left, right)nums[left], nums[rn] = nums[rn], nums[left]pivot = nums[left]le, ge = left+1, rightwhile True:while le<=ge and nums[le]<pivot:le += 1while le<=ge and nums[ge]>pivot:ge -= 1if le>=ge:breaknums[le], nums[ge] = nums[ge], nums[le]le += 1ge -= 1nums[left], nums[ge] = nums[ge], nums[left]return gelength = len(nums)target = length - k left, right  = 0, length-1while True:pivot = partition(nums, left, right)if pivot==target:return nums[pivot]elif pivot<target:left = pivot+1else:right = pivot-1

时间复杂度O(n),空间复杂度O(1)

快排讲解&二路和三路排序过程 (超级推荐)
https://www.bilibili.com/video/BV19S4y187Rt?spm_id_from=333.788.recommend_more_video.0&vd_source=9c14f0916f2233888f50267fd1553056

502 IPO

因为利润都是非负的，所以每次都选择 当前可以选择的项目中利润最大的项目。
当前利润最大可以通过堆实现，由于每完成一个项目的当前总资本就会变大，可以选择的项目可能会变多，注意到每个项目只能选择一次，如果没完成一个项目就要对剩下的项目遍历更新堆，元素会被重复访问多次，
所以可以先对于成本和利润进行排序，从而更新堆的过程中剩下的项目只需要遍历一次，代码如下

import heapq
class Solution:def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:temp = [(capital[i],-profits[i]) for i in range(len(profits))]temp.sort()cur = 0 t = []heapq.heapify(t)for _ in range(k):while cur<len(capital):if temp[cur][0]<=w:heapq.heappush(t,temp[cur][1])cur += 1else:breakif not t:breakw -= heapq.heappop(t)# w -= a[1]return w

时间复杂度：时间复杂度：O((n+k)logn)，其中 n 是数组 profits 和 capital 的长度，k 表示最多的选择数目。我们需要 O(nlogn) 的时间复杂度来来创建和排序项目，往堆中添加元素的时间不超过 O(nlogn)，每次从堆中取出最大值并更新资本的时间为 O(klogn)，因此总的时间复杂度为 O(nlogn+nlogn+klogn)=O((n+k)logn)

空间复杂度：O(n)

373 寻找和最小的k组数

直接构建所有可能的数组，然后排序后输出最小的k个

存在用例超出时间限制

多路归并的方法 来自宫水三叶

令 nums1 的长度为 n，nums2 的长度为 m，所有的点对数量为 n×m。

其中每个 nums1[i] 参与所组成的点序列为：

[(nums1[0],nums2[0]),(nums1[0],nums2[1]),…,(nums1[0],nums2[m−1])]

[(nums1[1],nums2[0]),(nums1[1],nums2[1]),…,(nums1[1],nums2[m−1])]

[(nums1[n−1],nums2[0]),(nums1[n−1],nums2[1]),…,(nums1[n−1],nums2[m−1])]

由于 nums1 和 nums2 均已按升序排序，因此每个 nums1[i] 参与构成的点序列也为升序排序，这引导我们使用「多路归并」来进行求解。

具体的，起始我们将这 n 个序列的首位元素（点对）以二元组 (i,j) 放入优先队列（小根堆），其中 i 为该点对中 nums1[i] 的下标，j 为该点对中 nums2[j] 的下标，这步操作的复杂度为 O(nlogn)。这里也可以得出一个小优化是：我们始终确保 nums1 为两数组中长度较少的那个，然后通过标识位来记录是否发生过交换，确保答案的点顺序的正确性。

每次从优先队列（堆）中取出堆顶元素（含义为当前未被加入到答案的所有点对中的最小值），加入答案，并将该点对所在序列的下一位（如果有）加入优先队列中。

举个 🌰，首次取出的二元组为 (0,0)，即点对 (nums1[0],nums2[0])，取完后将序列的下一位点对 (nums1[0],nums2[1]) 以二元组 (0,1) 形式放入优先队列。

可通过「反证法」证明，每次这样的「取当前，放入下一位」的操作，可以确保当前未被加入答案的所有点对的最小值必然在优先队列（堆）中，即前 k 个出堆的元素必然是所有点对的前 k 小的值。

import heapq
class Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:ans = []len1, len2 = len(nums1), len(nums2)# 注意，为了降低堆的大小提升运行效率，想要保持nums1是长度更小的，所以不满足的时候nums1和nums2进行了对换，注意到对应的数组长度也对应变了# 但是最终输出的结果需要按照原本nums1和nums2的结果来，所以需要有flag标识放入结果中应该按照什么样的顺序flag = len1>len2if len1>len2:len1, len2, nums1, nums2 = len2,len1, nums2, nums1pq = []for i in range(len1):heapq.heappush(pq, (nums1[i]+nums2[0], i, 0))for _ in range(k):_, a, b = heapq.heappop(pq)ans.append([nums1[a], nums2[b]] if not flag else [nums2[b], nums1[a]])if b+1<len2:heapq.heappush(pq, (nums1[a]+nums2[b+1], a, b+1))return ans

时间复杂度：令 M 为 n、m 和 k 三者中的最小值，复杂度为 O((M+k)logM)
空间复杂度：O(M)

295 数据流中位数

按照中位数的定义只需要获取到排序后中间位置的值，这里有大小和位置的两个限定，如果通过两个堆分别维护当前数和当前数的负数，堆顶分别是对应的最小值和最大值，同时要求两个堆元素个数要相同，不同时只能向后者添加元素，此时通过堆顶就可以获得排序后最中间的两个数，按照总数量的奇偶性输出结果，代码如下

注意到，增加元素的时候，虽然知道最终应该是哪个堆应该多一个元素，但是新元素和现有元素的大小其实没有确定，即真正应该增加到堆中的元素没有确定，所以add中需要先向另一个堆增加元素以找到真正应该增加到另一个堆的元素

class MedianFinder:def __init__(self):self.min_ = []self.max_ = []def addNum(self, num: int) -> None:if len(self.min_)!=len(self.max_):heappush(self.min_, -num)heappush(self.max_, -heappop(self.min_))else:heappush(self.max_, num)heappush(self.min_, -heappop(self.max_))def findMedian(self) -> float:if len(self.min_)!=len(self.max_):return -self.min_[0]else:return (self.max_[0]-self.min_[0])/2

当前元素个数n，则增加一个数字时间复杂度是O(logn)，找到中位数时间复杂度是O(1)

空间复杂度是O(n)