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

小半 • 2023年1月16日下午3:29 • 技术随笔 • 阅读 84

堆的概念

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

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

尾部插入
- 比父节点大就和父节点交换递归向上调整
- 这个过程称为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个数

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]

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)

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])

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]