设计最小/最大优先级队列

Question

我需要设计一个最小/最大优先级队列 插入，删除最大值，并删除最小值（全部在对数时间内）; 并找到最大值并找到最小值（均在常量时间内）。

Answer 1

方法1：

由于amit，带领你通过讨论，维护两个堆和记住指针元素。

方法2：（优于）

有用于此目的的数据结构特异性。它叫Min-Max Heap。类似地，也有相同规格的Max-Min Heap。

规格是按照你想要的东西：

1）插入 - O（LOGN）

2）DeleteMin - O（LOGN）

3）DeleteMax - O（LOGN ）

4.）创建 - O（n）的

5.）FindMin - O（1）

6）FindMax - O（1）

一些参考：

Min-Max Heap

How to perform a general deletion operation on a min-max heap?