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

class MedianFinder {
private:
    priority_queue<int> left;          // 大根堆，存较小的一半（默认大根堆）
    priority_queue<int, vector<int>, greater<int>> right; // 小根堆，存较大的一半

public:
    void addNum(int num) {
        // 先决定放哪个堆
        if (left.empty() || num <= left.top()) {
            left.push(num);           // 比左堆顶小，放左堆
        } else {
            right.push(num);          // 否则放右堆
        }

        // 调整平衡：left 可以比 right 多一个，但不能少
        if (left.size() > right.size() + 1) {
            // left 太大，移一个到 right
            right.push(left.top());
            left.pop();
        } else if (right.size() > left.size()) {
            // right 太大，移一个到 left
            left.push(right.top());
            right.pop();
        }
    }

    double findMedian() {
        if (left.size() > right.size()) {
            return left.top();        // 奇数个，中位数在左堆顶
        } else {
            return (left.top() + right.top()) / 2.0; // 偶数个，两堆顶平均值
        }
    }
};

int main() {
    MedianFinder mf;
    vector<int> nums = {5, 3, 8, 1, 9, 2, 7, 4, 6};
    for (int num : nums) {
        mf.addNum(num);
        cout << "加入 " << num << " 后中位数: " << mf.findMedian() << endl;
    }
    return 0;
}

import heapq

class MedianFinder:
    def __init__(self):
        self.left = []   # 大根堆，Python用负数模拟（存 -num）
        self.right = []  # 小根堆，正常存 num

    def addNum(self, num):
        # 先决定放左还是右
        if not self.left or num <= -self.left[0]:
            heapq.heappush(self.left, -num)   # 存入负数，让堆顶是最大的数（负值最小）
        else:
            heapq.heappush(self.right, num)

        # 平衡
        if len(self.left) > len(self.right) + 1:
            # left 多了，移一个到 right
            heapq.heappush(self.right, -heapq.heappop(self.left))
        elif len(self.right) > len(self.left):
            # right 多了，移一个到 left
            heapq.heappush(self.left, -heapq.heappop(self.right))

    def findMedian(self):
        if len(self.left) > len(self.right):
            return -self.left[0]               # 取出时取负
        else:
            return (-self.left[0] + self.right[0]) / 2.0

# 测试
mf = MedianFinder()
nums = [5, 3, 8, 1, 9, 2, 7, 4, 6]
for num in nums:
    mf.addNum(num)
    print(f"加入 {num} 后中位数: {mf.findMedian()}")

import heapq

def merge_fruits(weights):
    """
    :param weights: list[int] 每堆果子的重量
    :return: int 最小总体力
    """
    heapq.heapify(weights)               # 将列表转为小根堆，O(n)
    total_cost = 0                        # 总消耗体力
    while len(weights) > 1:               # 只要还有多于一堆
        a = heapq.heappop(weights)        # 最轻的第一堆
        b = heapq.heappop(weights)        # 第二轻的堆
        cost = a + b                      # 合并消耗
        total_cost += cost                # 累加
        heapq.heappush(weights, cost)     # 新堆放回
    return total_cost

# 测试
weights = [1, 2, 3, 4, 5]
print("最小总体力:", merge_fruits(weights))  # 输出 33

import heapq

def topK(nums, k):
    """
    从 nums 中找出最大的 k 个数
    :param nums: list[int]
    :param k: int
    :return: list[int]
    """
    if k <= 0 or not nums:
        return []
    min_heap = []
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)       # 堆没满，直接加入
        else:
            if num > min_heap[0]:               # 比堆顶大，替换
                heapq.heapreplace(min_heap, num) # 相当于 pop + push
    return min_heap

# 测试
nums = [10, 3, 7, 2, 9, 5, 8, 1, 4, 6]
print("最大的 3 个数:", topK(nums, 3))  # 输出可能是 [8, 9, 10]（顺序不保证）

import heapq

def dijkstra(graph, start):
    """
    graph: 邻接表，graph[u] = [(v, w)] 表示 u->v 权重 w
    start: 起点
    return: dist 数组，dist[i] 为起点到 i 的最短距离
    """
    n = len(graph)
    INF = 10**9
    dist = [INF] * n
    dist[start] = 0
    heap = [(0, start)]          # (距离, 节点)
    visited = [False] * n

    while heap:
        d, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

import heapq

def process_tasks(tasks):
    """
    tasks: list of (priority, duration)
    优先级数字越大越重要
    返回完成所有任务需要的时间（假设串行执行）
    """
    # 用负号实现大根堆，因为 Python 默认是小根堆
    heap = [(-p, d) for p, d in tasks]
    heapq.heapify(heap)
    time = 0
    while heap:
        neg_p, duration = heapq.heappop(heap)
        # 模拟执行该任务
        time += duration
        print(f"处理优先级为 {-neg_p} 的任务，耗时 {duration}，当前时间 {time}")
    return time

# 测试
tasks = [(3, 5), (1, 2), (5, 3), (2, 4)]
print("总耗时:", process_tasks(tasks))