题目链接

两端问优先队列

题目描述

你需要实现一个数据结构，支持对一个整数序列（初始为空）进行五种操作：

  1. 插入 x: 1 x
  2. 查询最小值: 2
  3. 查询最大值: 3
  4. 删除最小值: 4 (若有多个，只删除一个)
  5. 删除最大值: 5 (若有多个，只删除一个)

这是一个主函数模式的题目，你需要自己处理输入和输出。

输入格式:

  • 第一行是一个整数 ，表示操作的总数。
  • 接下来 行，每行描述一个操作。

输出格式:

  • 对于每个查询操作（类型 2 和 3），输出一行，为查询结果。

示例: 输入:

10
1 97
3
5
1 78
3
5
1 68
3
5
1 49

输出:

97
78
68

解题思路

单个优先队列（堆）只能高效地处理一端（要么是最小，要么是最大）。当我们需要同时对两端进行查询和删除时，就需要更高级的数据结构或组合方法。

方法一：平衡二叉搜索树 (C++/Java)

对于 C++ 和 Java，最简洁高效的方法是使用标准库中基于**平衡二叉搜索树（Balanced Binary Search Tree）**的有序集合。

  • C++: std::multiset 是完美的选择。它是一个允许重复元素的红黑树，内部始终有序。
    • 插入: s.insert(x) -
    • 查询最小: *s.begin() -
    • 查询最大: *s.rbegin() -
    • 删除最小: s.erase(s.begin()) -
    • 删除最大: s.erase(std::prev(s.end())) -
  • Java: java.util.TreeMap 可以用来模拟多重集合。我们将数字作为键（Key），其出现的次数作为值（Value）。TreeMap 内部也是一个红黑树，保证了键的有序性。
    • 插入: 更新 map.get(x) 的频率 -
    • 查询最小: map.firstKey() -
    • 查询最大: map.lastKey() -
    • 删除最小/最大: 获取 firstKey/lastKey，然后更新其频率。如果频率降为0，则从 map 中移除该键 - 。

方法二：双堆 + 哈希表 (Python)

Python 的标准库中没有内置的平衡二叉搜索树，因此最常用的方法是双堆（Two Heaps）。

  1. 一个最小堆 min_heap：用于快速找到和删除最小值。
  2. 一个最大堆 max_heap：用于快速找到和删除最大值。（在 Python 中用 heapq 存入负数来模拟）。
  3. 一个哈希表 counts：用于记录每个数字的存活数量。

这个方法的核心是延迟删除 (Lazy Deletion)：

  • 插入 x: 将 x 推入 min_heap，将 -x 推入 max_heap，并增加 counts[x]。
  • 删除最小: 从 min_heap 弹出堆顶元素 val，然后减少 counts[val]。
  • 删除最大: 从 max_heap 弹出堆顶元素 -val，然后减少 counts[val]。
  • 查询最小: 查看 min_heap 的堆顶 val。如果 counts[val] 为 0，说明这个元素已经被从另一端删除了，所以直接从 min_heap 弹出并继续查看下一个，直到找到一个 counts 大于 0 的元素。这个元素就是当前的真·最小值。
  • 查询最大: 对 max_heap 执行类似的操作。

这种方法巧妙地解决了在一个堆中删除元素，如何在另一个堆中同步的问题。

代码

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    multiset<int> s;

    for (int i = 0; i < n; ++i) {
        int op;
        cin >> op;
        switch(op) {
            case 1: {
                int x;
                cin >> x;
                s.insert(x);
                break;
            }
            case 2: {
                if (!s.empty()) {
                    cout << *s.begin() << "\n";
                }
                break;
            }
            case 3: {
                if (!s.empty()) {
                    cout << *s.rbegin() << "\n";
                }
                break;
            }
            case 4: {
                if (!s.empty()) {
                    s.erase(s.begin());
                }
                break;
            }
            case 5: {
                if (!s.empty()) {
                    s.erase(prev(s.end()));
                }
                break;
            }
        }
    }
    return 0;
}

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        TreeMap<Integer, Integer> map = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            int op = sc.nextInt();
            switch (op) {
                case 1: {
                    int x = sc.nextInt();
                    map.put(x, map.getOrDefault(x, 0) + 1);
                    break;
                }
                case 2: {
                    if (!map.isEmpty()) {
                        System.out.println(map.firstKey());
                    }
                    break;
                }
                case 3: {
                    if (!map.isEmpty()) {
                        System.out.println(map.lastKey());
                    }
                    break;
                }
                case 4: {
                    if (!map.isEmpty()) {
                        int minKey = map.firstKey();
                        int count = map.get(minKey);
                        if (count == 1) {
                            map.remove(minKey);
                        } else {
                            map.put(minKey, count - 1);
                        }
                    }
                    break;
                }
                case 5: {
                    if (!map.isEmpty()) {
                        int maxKey = map.lastKey();
                        int count = map.get(maxKey);
                        if (count == 1) {
                            map.remove(maxKey);
                        } else {
                            map.put(maxKey, count - 1);
                        }
                    }
                    break;
                }
            }
        }
    }
}

import heapq
from collections import Counter

def main():
    n = int(input())
    min_heap = []
    max_heap = []
    counts = Counter()

    for _ in range(n):
        line = list(map(int, input().split()))
        op = line[0]

        if op == 1:
            x = line[1]
            if counts[x] == 0:
                heapq.heappush(min_heap, x)
                heapq.heappush(max_heap, -x)
            counts[x] += 1
        elif op == 2: # Get Min
            while min_heap and counts[min_heap[0]] == 0:
                heapq.heappop(min_heap)
            if min_heap:
                print(min_heap[0])
        elif op == 3: # Get Max
            while max_heap and counts[-max_heap[0]] == 0:
                heapq.heappop(max_heap)
            if max_heap:
                print(-max_heap[0])
        elif op == 4: # Pop Min
            while min_heap and counts[min_heap[0]] == 0:
                heapq.heappop(min_heap)
            if min_heap:
                val = min_heap[0]
                counts[val] -= 1
        elif op == 5: # Pop Max
            while max_heap and counts[-max_heap[0]] == 0:
                heapq.heappop(max_heap)
            if max_heap:
                val = -max_heap[0]
                counts[val] -= 1

if __name__ == "__main__":
    main()

算法及复杂度

  • 平衡二叉搜索树 (C++/Java) 方案
    • 时间复杂度: 。每次操作（插入、删除、查询）的复杂度都是 ，其中 是集合中元素的数量。
    • 空间复杂度: ，用于存储所有插入的元素。
  • 双堆 (Python) 方案
    • 时间复杂度: 。插入是 。查询和删除操作虽然包含一个 while 循环，但每个元素最多只会被压入和弹出常数次，因此均摊（Amortized）复杂度也是 。
    • 空间复杂度: ，两个堆和一个哈希表最多存储 个元素。