堆

堆专题（上） | 力扣加加 - 努力做西湖区最好的算法题解

一个中心

动态求极值

四大应用

1. topK
2. 带权最短距离
3. 因子分解
4. 堆排序

元组 + 堆

实现堆 + 元组排序

大顶堆

负数即可

313. 超级丑数 - 力扣（LeetCode）

题目描述：超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数

• 方法一： 使用小顶堆
• 方法二：
• 方法三：
  注意：
  要熟悉 heapq 库的用法

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        heap = [1]
        heapq.heapify(heap)
        for i in range(n):
            curr_min = heapq.heappop(heap)
            while len(heap) > 0 and curr_min == heap[0]:
                heapq.heappop(heap)
            for i in range(len(primes)):
                heapq.heappush(heap, primes[i] * curr_min)
        return curr_min

1738. 找出第 K 大的异或坐标值 - 力扣（LeetCode）

295. 数据流的中位数 - 力扣（LeetCode）

import heapq
class MedianFinder:
    def __init__(self):
       self.left_heap = []
       self.right_heap =[]
       heapq.heapify(self.left_heap)
       heapq.heapify(self.right_heap)
    def addNum(self, num: int) -> None:
        if(len(self.left_heap)<=len(self.right_heap)):
          heapq.heappush(self.left_heap,-num)
        else:
          heapq.heappush(self.right_heap,num)
        if(len(self.right_heap)!=0 and -1*self.left_heap[0]>self.right_heap[0]):
           min_left_headp = heapq.heappop(self.left_heap)
           min_right_headp = heapq.heappop(self.right_heap)
           heapq.heappush(self.left_heap,-1*min_right_headp)
           heapq.heappush(self.right_heap,-1*min_left_headp)
    def findMedian(self) -> float:
        if(len(self.left_heap)>len(self.right_heap)):
           return -1*self.left_heap[0]
        else:
           return (-1*self.left_heap[0]+ self.right_heap[0])/2