堆

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

一个中心

动态求极值

四大应用

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

大(小)根堆算法操作可视化

模板题

Kth Largest Element in a Stream - LeetCode

class KthLargest {
    constructor(k, nums) {
        this.k = k;
        this.minHeap = new MinPriorityQueue();
        for (let num of nums) {
            this.add(num);
        }
    }

    add(val) {
        if (this.minHeap.size() < this.k) {
            this.minHeap.enqueue(val);
        } else if (val > this.minHeap.front().element) {
            this.minHeap.dequeue();
            this.minHeap.enqueue(val);
        }
        return this.minHeap.front().element;
    }
}

var KthLargest = function(k, nums) {
    this.k = k;
    this.heap = [];
    for (let num of nums) {
        this.add(num);
    }
};

KthLargest.prototype.add = function(val) {
    if (this.heap.length < this.k) {
        this.heap.push(val);
        this.heap.sort((a, b) => a - b); // 保持排序
    } else if (val > this.heap[0]) {
        this.heap[0] = val;
        this.heap.sort((a, b) => a - b); // 重新排序
    }
    return this.heap[0];
};