求设计支持指定时间复杂度操作的数据结构及实现思路

首选方案：双堆+计数字典 #

用最小堆专门处理最小值相关操作，最大堆处理最大值相关操作，再搭配一个字典（哈希表）记录每个元素当前的有效数量——解决两个堆元素不同步的问题（比如某个元素已被删除，但仍留在其中一个堆内）。

各操作具体实现 #

1. Init(A, n)

   • 直接用堆化（heapify）算法将数组A分别构建成最小堆和最大堆，堆化的时间复杂度为O(n)，完全符合要求。
   • 遍历数组A，用字典统计每个元素的出现次数。

2. insert(x)

   • 将x分别插入最小堆和最大堆，堆插入操作的时间复杂度为O(logn)。
   • 在字典中对x的计数加1（若x未在字典中，则初始化为1）。

3. find_min()

   • 检查最小堆的堆顶元素：若字典中该元素的计数大于0，直接返回；若计数为0，说明该元素已被全部删除，将其从堆顶弹出，继续检查下一个堆顶，直到找到计数>0的元素。该操作均摊时间复杂度为O(1)，因为每个元素最多被弹出一次。

4. find_max()

   • 与find_min()逻辑对称：检查最大堆的堆顶元素，有效则返回，无效则弹出堆顶，直到找到有效的最大元素，均摊时间复杂度O(1)。

5. extract_min()

   • 先用find_min()的逻辑定位当前有效的最小元素x。
   • 将字典中x的计数减1，若计数变为0则从字典中移除该键。
   • 返回x，整个操作的时间复杂度为O(logn)（主要来自堆弹出操作）。

6. extract_max()

   • 与extract_min()逻辑对称：定位有效最大元素x，减少计数后返回，时间复杂度O(logn)。

替代方案：平衡二叉搜索树 #

像红黑树、AVL树这类平衡BST，天生支持O(logn)的插入与删除操作，且能直接以O(1)时间获取最小（最左节点）和最大（最右节点）元素。

• Init(A,n)：使用线性时间算法将数组构建为平衡BST，时间复杂度O(n)。
• 其他操作直接利用BST特性：insert为O(logn)，find_min/find_max直接取首尾节点为O(1)，extract_min/extract_max删除首尾节点为O(logn)。
• 优势是无需额外维护字典，逻辑更简洁；缺点是手动实现平衡BST成本极高，若使用语言自带的有序集合（如Python的SortedList、Java的TreeSet）可直接复用，自行开发则难度较大。

实现注意事项 #

• 双堆方案中，堆内会存在“无效元素”（已被删除但未弹出的元素），但因每个元素最多被弹出一次，整体时间复杂度仍符合要求，无需过度纠结。
• 字典的计数需准确维护，避免出现计数为负或更新遗漏的情况。
• 若处理无重复元素的集合，字典可简化为记录元素是否存在即可。
• 初始化时必须使用堆化算法，不能采用逐个插入堆的方式（逐个插入为O(nlogn)），才能达到O(n)的时间要求。

内容的提问来源于stack exchange，提问作者Mia