如何进一步优化此数据结构？

Question

我最近被要求构建一个支持四种操作的数据结构,即

1. 推送:向DS添加元素.
2. Pop:删除最后推送的元素.
3. Find_max:查找当前存储元素中的最大元素.
4. Pop_max:从DS中删除最大元素.

元素是整数.

这是我建议的解决方案:

1. 筹码.
2. 在其中存储一对元素.该对应(元件,max_so_far),其中元件是该索引处的元件和max_so_far是迄今所看到的最大值元素.
3. 在将元素推入堆栈时,检查最顶层堆栈元素的max_so_far.如果当前数字大于该值,则将当前对的max_so_far值作为当前元素的值,否则存储先前的max_so_far.这意味着推动只是一种O(1)操作.
4. 因为pop,只需从堆栈中弹出一个元素.同样,这个操作是O(1).
5. 对于Find_max,返回堆栈中最顶层元素的max_so_far的值.再次,O(1).
6. 弹出max元素将涉及遍历堆栈并在分配新的max_so_far值后显式删除max元素并推回其顶部的元素.这将是线性的.

我被要求改进它,但我不能.

在时间复杂度方面,如果所有操作都发生,总体时间可以改善O(logn),我想.怎么做,是我无法得到的.

Answer 1

一种方法是将指针存储到双向链表中的元素,也存储在最大堆数据结构中(按值排序).

每个元素都将其位置存储在双向链表中以及最大堆中.

在这种情况下,所有操作在双向链表中需要O(1)时间,在堆数据结构中需要O(log(n))时间.

Answer 2

获得O(log n)-time操作的一种方法是混合两个数据结构,在这种情况下是双向链表和优先级队列(配对堆是一个不错的选择).我们有一个类似的节点结构

struct Node {
    Node *previous, *next;  // doubly linked list
    Node **back, *child, *sibling;  // pairing heap
    int value;
} list_head, *heap_root;

现在,为了推动,我们推进两种结构.对于find_max,我们返回配对堆的根值.对于pop或pop_max,我们从适当的数据结构中弹出,然后使用其他节点指针在其他数据结构中删除.