堆与优先队列

import heapq

# 建堆：O(n) 原地把无序数组变成最小堆
arr = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(arr)                       # arr 现在满足堆性质

# push：O(log n)
heapq.heappush(arr, 0)

# 看顶：O(1)，arr[0] 就是当前最小
top = arr[0]

# 弹顶：O(log n)
smallest = heapq.heappop(arr)

# heapreplace = pop + push 一步合成，只走一次下沉，比分开快
# 注意：先返回旧顶、再压入新元素
old_top = heapq.heapreplace(arr, 7)

import java.util.PriorityQueue;
import java.util.List;

// 建堆：传入 Collection 是 O(n)；逐个 offer 是 O(n log n)
PriorityQueue<Integer> heap = new PriorityQueue<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));

// push：O(log n)
heap.offer(0);

// 看顶：O(1)
int top = heap.peek();

// 弹顶：O(log n)
int smallest = heap.poll();

// Java 没有 heapreplace，等价写法是 poll() + offer() 两步
// 实际开销是两次 sift（一次下沉 + 一次上浮），略慢于 Python heapreplace
heap.poll();
heap.offer(7);

#include <queue>
#include <vector>
using namespace std;

// 默认是最大堆——要最小堆得显式 greater<int>
priority_queue<int, vector<int>, greater<int>> heap;

// 批量建堆：直接用 vector 构造，O(n)
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
priority_queue<int, vector<int>, greater<int>> heap2(arr.begin(), arr.end());

// push：O(log n)
heap.push(0);

// 看顶：O(1)
int top = heap.top();

// 弹顶：O(log n)
heap.pop();

// 同样没有 heapreplace，要 pop 后 push
heap.pop();
heap.push(7);

import heapq

def top_k_largest(nums: list[int], k: int) -> list[int]:
    """返回前 k 大的元素（顺序不定）；堆顶 = 第 k 大"""
    heap = []                                    # 最小堆
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)              # 堆没满，直接放
        elif x > heap[0]:
            heapq.heapreplace(heap, x)           # 比门槛大，替换堆顶
    return heap                                  # 堆里就是 Top-K

import java.util.PriorityQueue;

int[] topKLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();   // 默认最小堆
    for (int x : nums) {
        if (heap.size() < k) {
            heap.offer(x);
        } else if (x > heap.peek()) {
            heap.poll();
            heap.offer(x);                       // 没有 heapreplace，poll + offer
        }
    }
    int[] ans = new int[k];
    for (int i = 0; i < k; i++) ans[i] = heap.poll();
    return ans;
}

vector<int> topKLargest(vector<int>& nums, int k) {
    // 求第 k 大用最小堆——堆顶是 Top-K 里最小的"门槛"
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int x : nums) {
        if ((int)heap.size() < k) {
            heap.push(x);
        } else if (x > heap.top()) {
            heap.pop();
            heap.push(x);
        }
    }
    vector<int> ans;
    while (!heap.empty()) { ans.push_back(heap.top()); heap.pop(); }
    return ans;
}

import heapq

class MedianStream:
    def __init__(self):
        self.left = []                           # 最大堆（存 -x 模拟）
        self.right = []                          # 最小堆

    def add(self, x: int) -> None:
        # 三步走：先无脑放 left，再把 left 顶倒给 right，最后看是否回倒
        heapq.heappush(self.left, -x)
        heapq.heappush(self.right, -heapq.heappop(self.left))
        if len(self.right) > len(self.left):
            heapq.heappush(self.left, -heapq.heappop(self.right))

    def median(self) -> float:
        if len(self.left) > len(self.right):
            return -self.left[0]                 # 总数奇数：中位数在 left 顶
        return (-self.left[0] + self.right[0]) / 2

import java.util.PriorityQueue;
import java.util.Comparator;

class MedianStream {
    private final PriorityQueue<Integer> left;   // 最大堆
    private final PriorityQueue<Integer> right;  // 最小堆

    public MedianStream() {
        // 用 Comparator.reverseOrder() 避免 (a,b) -> b - a 的溢出
        left = new PriorityQueue<>(Comparator.reverseOrder());
        right = new PriorityQueue<>();
    }

    public void add(int x) {
        left.offer(x);
        right.offer(left.poll());
        if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }

    public double median() {
        if (left.size() > right.size()) {
            return left.peek();
        }
        return (left.peek() + right.peek()) / 2.0;
    }
}

class MedianStream {
    priority_queue<int> left;                                          // 默认最大堆
    priority_queue<int, vector<int>, greater<int>> right;              // 最小堆

public:
    void add(int x) {
        left.push(x);
        right.push(left.top()); left.pop();
        if (right.size() > left.size()) {
            left.push(right.top()); right.pop();
        }
    }

    double median() const {
        if (left.size() > right.size()) return left.top();
        return (left.top() + right.top()) / 2.0;
    }
};

class Solution:
    def findKthLargest_sort(self, nums: list[int], k: int) -> int:
        nums.sort()
        return nums[-k]

class Solution {
    public int findKthLargestSort(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

class Solution {
public:
    int findKthLargestSort(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        heap = []
        for x in nums:
            if len(heap) < k:
                heapq.heappush(heap, x)
            elif x > heap[0]:
                heapq.heapreplace(heap, x)       # pop + push 一步合成
        return heap[0]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int x : nums) {
            if (heap.size() < k) {
                heap.offer(x);
            } else if (x > heap.peek()) {
                heap.poll();
                heap.offer(x);
            }
        }
        return heap.peek();
    }
}

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;
        for (int x : nums) {
            if ((int)heap.size() < k) {
                heap.push(x);
            } else if (x > heap.top()) {
                heap.pop();
                heap.push(x);
            }
        }
        return heap.top();
    }
};

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = []
        for x in nums:
            self.add(x)                          # 复用 add，省得写两遍

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

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> heap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.heap = new PriorityQueue<>();
        for (int x : nums) {
            add(x);
        }
    }

    public int add(int val) {
        if (heap.size() < k) {
            heap.offer(val);
        } else if (val > heap.peek()) {
            heap.poll();
            heap.offer(val);
        }
        return heap.peek();
    }
}

class KthLargest {
    int k;
    priority_queue<int, vector<int>, greater<int>> heap;

public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) {
            add(x);                              // 复用 add，省得写两遍
        }
    }

    int add(int val) {
        if ((int)heap.size() < k) {
            heap.push(val);
        } else if (val > heap.top()) {
            heap.pop();
            heap.push(val);
        }
        return heap.top();
    }
};

import heapq

class MedianFinder:
    def __init__(self):
        self.left = []                           # 最大堆（存 -num 模拟）
        self.right = []                          # 最小堆

    def addNum(self, num: int) -> None:
        # 三步走：先入 left，再把 left 顶丢给 right，最后平衡
        heapq.heappush(self.left, -num)
        heapq.heappush(self.right, -heapq.heappop(self.left))
        if len(self.right) > len(self.left):
            heapq.heappush(self.left, -heapq.heappop(self.right))

    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return -self.left[0]                 # 奇数个，中位数在 left 顶
        return (-self.left[0] + self.right[0]) / 2

class MedianFinder {
    private final PriorityQueue<Integer> left;   // 最大堆
    private final PriorityQueue<Integer> right;  // 最小堆

    public MedianFinder() {
        left = new PriorityQueue<>(Comparator.reverseOrder());
        right = new PriorityQueue<>();
    }

    public void addNum(int num) {
        left.offer(num);
        right.offer(left.poll());
        if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }

    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        }
        return (left.peek() + right.peek()) / 2.0;
    }
}

class MedianFinder {
    priority_queue<int> left;                                          // 默认最大堆
    priority_queue<int, vector<int>, greater<int>> right;              // 最小堆

public:
    MedianFinder() {}

    void addNum(int num) {
        // 三步走：先入 left，再把 left 顶丢给 right，最后平衡
        left.push(num);
        right.push(left.top());
        left.pop();
        if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }

    double findMedian() {
        if (left.size() > right.size()) {
            return left.top();                   // 奇数个，中位数在 left 顶
        }
        return (left.top() + right.top()) / 2.0;
    }
};

from collections import Counter
import heapq

class LazyHeap:
    """支持 O(log n) push / O(log n) 摊还 pop / O(log n) 摊还 peek
    + O(1) 标记删除任意元素（必须确保该元素当前在堆中）"""

    def __init__(self):
        self.heap = []
        self.to_delete = Counter()
        self.size = 0  # 逻辑大小（已剔除标记删除）

    def push(self, x):
        heapq.heappush(self.heap, x)
        self.size += 1

    def remove(self, x):
        """标记删除 x；真正清理推迟到 peek/pop 时"""
        self.to_delete[x] += 1
        self.size -= 1

    def _clean_top(self):
        while self.heap and self.to_delete[self.heap[0]] > 0:
            self.to_delete[heapq.heappop(self.heap)] -= 1

    def peek(self):
        self._clean_top()
        return self.heap[0]

    def pop(self):
        self._clean_top()
        self.size -= 1
        return heapq.heappop(self.heap)

import java.util.*;

class LazyHeap {
    // 最小堆 + 延迟删除计数表
    private final PriorityQueue<Integer> heap = new PriorityQueue<>();
    private final Map<Integer, Integer> toDelete = new HashMap<>();
    private int size = 0;  // 逻辑大小（已剔除标记删除）

    public void push(int x) {
        heap.offer(x);
        size++;
    }

    /** 标记删除 x；真正清理推迟到 peek/pop 时。要求 x 当前在堆中 */
    public void remove(int x) {
        toDelete.merge(x, 1, Integer::sum);
        size--;
    }

    private void cleanTop() {
        while (!heap.isEmpty() && toDelete.getOrDefault(heap.peek(), 0) > 0) {
            int top = heap.poll();
            toDelete.merge(top, -1, Integer::sum);
        }
    }

    public int peek() {
        cleanTop();
        return heap.peek();
    }

    public int pop() {
        cleanTop();
        size--;
        return heap.poll();
    }

    public int size() { return size; }
}

#include <queue>
#include <unordered_map>

class LazyHeap {
    // 最小堆 + 延迟删除计数表
    priority_queue<int, vector<int>, greater<int>> heap;
    unordered_map<int, int> toDelete;
    int sz = 0;  // 逻辑大小（已剔除标记删除）

    void cleanTop() {
        while (!heap.empty() && toDelete[heap.top()] > 0) {
            toDelete[heap.top()]--;
            heap.pop();
        }
    }

public:
    void push(int x) { heap.push(x); sz++; }

    // 标记删除 x；真正清理推迟到 peek/pop 时。要求 x 当前在堆中
    void remove(int x) { toDelete[x]++; sz--; }

    int peek() { cleanTop(); return heap.top(); }

    int pop() {
        cleanTop();
        int x = heap.top();
        heap.pop();
        sz--;
        return x;
    }

    int size() const { return sz; }
};