具有快速最小、删除、插入、搜索大型计算作业的数据结构

对于这种用法，平衡树是一个非常好的数据结构。所有指定的操作都在 中计算。我认为您可以编写一个优化的树实现，以便可以检索最小值（通过将迭代器保留为最小值，并可能保留值以加快获取速度）。算法的结果时间将是 其中 是数据结构中的迭代次数和项目数。O(log n)O(1)O(m log n)mn

这是最佳的算法复杂性。事实上，假设每次迭代都可以在（摊销）中完成，那么这四个操作中的每一个也必须具有这样的复杂性。让我们假设可以使用这样的属性构建数据结构。可以编写以下算法（用 Python 编写）：O(1)S

def superSort(input):
    s = S()
    inputSize = len(input)
    for i in range(inputSize):
        s.insert(item[i])
    output = list()
    for i in range(inputSize):
        output.append(s.getMin())
        s.deleteMin()
    return output

superSort具有 的（摊销）复杂度。然而，基于比较的排序的理论上最优精确算法复杂度已被证明是 。因此，不可能存在，并且至少需要在一定时间内完成 4 个操作中的至少一个。O(n)O(n log (n))SO(log n)

请注意，朴素的二叉树实现通常效率非常低下。您可以执行很多优化来使它们更快。例如，您可以打包节点（参见 B 树），将节点放在数组中（假设项目的数量是有界的），使用可能基于随机属性的宽松平衡（参见 Treaps），使用小引用（例如 16 位索引或 32 位索引而不是 64 位指针）等。您可以从幼稚的 AVL 或张开树开始。

我建议的数据结构需要更多的工作才能实现，但它确实达到了预期的结果; 可以使用 AVL 树实现带有操作的数据结构，该树确保每个操作都在 O（1） 中完成并在 O（1） 中完成。{insert, delete, findMin, search}O(logn)findMin

我将深入探讨实现：

该树将包含指向最小节点的指针，该指针在每次插入和删除时都会更新，因此需要 .findMinO(1)

insert在每个 AVL 树中都按原样实现（使用平衡因子和旋转/交换来平衡树）。插入元素后，需要通过从树根一直到左侧来更新最小节点指针，这也需要，因为树的高度是 。O(logn)O(logn)O(logn)

同样，使用后，您需要以相同的方式更新最小指针，因此它需要 .deleteO(logn)

最后，还需要.searchO(logn)

如果给出了更多的假设，例如插入的元素在最小值的某个范围内，那么你也可以给出树中的每个节点和指针，这些指针也可以在插入和删除过程中更新，因此可以在不需要遍历整个树的情况下访问。搜索插入的元素可以更快地完成。successorpredecessorO(logn)O(1)

插入节点的后继节点可以通过转到右侧子节点，然后一直转到左侧来更新。但是，如果不存在右子节点，那么只要当前节点不是其父节点的左子节点，就需要爬上父节点。 前身以完全相反的方式更新。

在 c++ 中，节点如下所示

template <class Key,class Value>
class AvlNode{
private:
    Key key;
    Value value;
    int Height;
    int BF; //balance factor
    AvlNode* Left;
    AvlNode* Right;
    AvlNode* Parent;
    AvlNode* Succ;
    AvlNode* Pred;

public:
...
}

虽然这棵树看起来像这样：

template <class Key,class Value>
class AVL {
private:
    int NumOfKeys;
    int Height;
    AvlNode<Key, Value> *Minimum;
    AvlNode<Key, Value> *Root;

    static void swapLL(AVL<Key, Value> *avl, AvlNode<Key, Value> *root);
    static void swapLR(AVL<Key, Value> *avl, AvlNode<Key, Value> *root);
    static void swapRL(AVL<Key, Value> *avl, AvlNode<Key, Value> *root);
    static void swapRR(AVL<Key, Value> *avl, AvlNode<Key, Value> *root);

public:
...
}

从你告诉我们的情况来看，我想我会使用一个开放寻址的哈希表进行搜索，并使用堆来跟踪最小值。

在堆中，您将存储指向哈希表中项的索引/指针，而不是存储值。这样，当您从堆中删除 min 时，您可以按照指针从哈希表中找到需要删除的项目。

每个项目的总内存开销为 3 或 4 个单词 - 与平衡树大致相同，但实现更简单、更快。