設計最小/最大優先級隊列

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?