数据结构-堆基本应用刷题

堆的概念

• 一种基于完全二叉树的结构
• 大顶堆和小顶堆
  大顶堆 —— 任意的三元组，父节点都大于两个子节点
  小顶堆 —— 任意的三元组，父节点都小于两个子节点
  根节点为最大值或最小值
• 堆适合维护集合的最值

堆的基本操作（以大顶堆为例）

• 尾部插入

  • 比父节点大就和父节点交换 递归向上调整
  • 这个过程称为SIFT-UP

• 头部弹出

  • 用最后一个元素（叶子结点）补位 递归向下调整
  • 这个过程称为SIFT-DOWN

堆的基础应用

剑指 Offer 40. 最小的k个数

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        # python 中存储的是小顶堆   进行取负值操作
        arr = [-num for num in arr] 
        heap = arr[:k]
        heapq.heapify(heap) # 将list 转换为heap 
        for num in arr[k:]:
            if num > heap[0]: #  选后面负数进行 大小的比较 大的入堆 
                heapq.heapreplace(heap, num)
        return [-num for num in heap]  # 遍历堆， 取反 返回最小的K个数
1
2
3
4
5
6
7
8
9
10
11
12

1046. 最后一块石头的重量

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [-stone for stone in stones]
        heapq.heapify(stones)
        while len(stones) > 1:
            x = stones[0]      
            heapq.heappop(stones)   # heappop 弹出 heapq第一个值 
            y = stones[0]
            heapq.heappop(stones)  # heappop 弹出 heapq第一个值 
            if x - y != 0:
                heapq.heappush(stones,x -y)
        if len(stones) == 0:
            return 0
        return  -stones[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

703. 数据流中的第 K 大元素

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        if k > len(nums):
            self.heap = nums
            heapq.heapify(self.heap)
        else:
            self.heap = nums[:k]
            heapq.heapify(self.heap)
            for num in nums[k:]:
                if num > self.heap[0]:
                    heapq.heapreplace(self.heap, num)
                

    def add(self, val: int) -> int:
        if self.k > len(self.heap):
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap,val)
        return self.heap[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

373. 查找和最小的 K 对数字

目前出现的问题就是超时

num_tuple = [(u, v) for u in nums1 for v in nums2]
return heapq.nsmallest(k, num_tuple, key=lambda s: s[0] + s[1])

1
2
3

215. 数组中的第K个最大元素

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

1
2
3
4
5
6
7
8
9
10