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

Question

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

1. 推送：向DS添加元素

元素是整数。

以下是我建议的解决方案：

1. 拿一堆
2. 在其中存储一对元素。这对应该是（element，max_so_far），其中element是该索引处的元素，max_so_far是迄今为止看到的最大值元素
3. 将元素推入堆栈时，请检查最顶层堆栈元素的max\u so\u far。如果当前数大于该值，则将当前对的max\u so\u far值作为当前元素的值，否则存储以前的max\u so\u far。这意味着推送将只是一个O（1）操作
4. 对于pop，只需从堆栈中弹出一个元素。同样，该操作是O（1）
5. 对于Find\u max，返回堆栈中最顶层元素的max\u so\u far值。同样，O（1）
6. 弹出max元素将涉及遍历堆栈，明确删除max元素，并在分配新的max\u so\u far值后将其顶上的元素推回。这将是线性的

我被要求改进它，但我做不到。

就时间复杂度而言，我猜想，如果所有操作都发生在O（logn）中，则总体时间可以得到改善。如何做到这一点，是我无法做到的。

Answer 1

通常，当您需要按质量A（值）和质量B（插入顺序）查找元素时，您开始关注一个数据结构，该数据结构实际上内部有两个相互引用的数据结构，或者以其他方式交错。

例如：两个映射，谁的键是质量A和质量B，谁的值是指向结构的共享指针，该结构包含返回两个映射的迭代器和值。然后你有log（n）通过任一质量查找元素，擦除是~O（logn）从任一映射中删除两个迭代器。

struct hybrid {
    struct value {
        std::map<std::string, std::shared_ptr<value>>::iterator name_iter;
        std::map<int, std::shared_ptr<value>>::iterator height_iter;
        mountain value;
    };
    std::map<std::string, std::shared_ptr<value>> name_map;
    std::map<int, std::shared_ptr<value>> height_map;

    mountain& find_by_name(std::string s) {return name_map[s]->value;}
    mountain& find_by_height(int height h) {return height_map[s]->value;}
    void erase_by_name(std::string s) {
        value& v = name_map[s];
        name_map.erase(v.name_iter);
        height_iter.erase(v.height_iter); //note that this invalidates the reference v
    }
};

然而，在您的情况下，您可以做得比这个O（logn）更好，因为您只需要“最近的”和“次高的”。要使“pop highest”快速，您需要一种快速方法来检测下一个最高值，这意味着需要在插入时预先计算。要找到相对于其余部分的“高度”位置，需要某种类型的地图。要使“pop-most-recent”快速，您需要一种快速的方法来检测下一个最新的，但这是微不足道的计算。我建议创建一个映射或节点堆，其中键是查找最大值的值，值是指向下一个最新值的指针。这将提供O（logn）插入、O（1）查找最近值、O（1）或O（logn）查找最大值（取决于实现），以及~ O（logn）通过任一索引进行擦除。

Answer 2

获得O（log n）时间操作的一种方法是将两个数据结构混合在一起，在这种情况下，是一个双链表和一个优先级队列（配对堆是一个不错的选择）。我们有一个节点结构，比如

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

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

Answer 3

一种方法是将指向元素的指针存储在双链表中，也可以存储在最大堆数据结构中（按值排序）。

每个元素都将其位置存储在双链表和max-heap中。

在这种情况下，所有操作都需要在双链表中花费O（1）时间，加上堆数据结构中的O（log（n））时间。