我目前有一个按降序排序的对象双链表。 (该列表是侵入性的——对象中的指针。)我的操作集非常有限:
- 添加一个具有最高键的节点
- 删除具有最高可能键的节点(无论是哪一个)
- 删除键为 0 的节点(无论哪个节点)
- 递增具有最高当前 key 的节点的 key (与哪个节点无关)
- 递减 任何给定 键大于 0 的节点的键
操作 1-4 将是常数时间，但操作 5 是 O(n)，其中 n = 具有相同键值的节点数。这是因为此类节点在递增时必须移过它们具有相同键值的兄弟节点，并放置在该范围之后。找到重新插入的位置将是 O(n)。
我认为堆(heapsort 堆，而不是 malloc 堆)是最坏情况为 O(log n)(其中 n=节点数)的解决方案。然而，根据我的记忆和谷歌的发现，它似乎总是在数组中实现，而不是二叉树。所以:
问题:是否有一个以二叉树的方式使用指针的堆的实现，而不是一个数组，它维护典型数组实现的 O()？
最佳答案
一种常见的方法是使用基于数组的堆，但是:
- 在堆中存储指向节点的指针；
- 在每个节点中，您将其索引存储在堆中；和
- 每当交换堆中的元素时，都会更新相应节点中的索引；
这保留了所有堆操作的复杂性，并且每个节点花费大约 1.5 个指针和 1 个整数。 (额外的 .5 是因为可增长数组的实现方式)。
或者，您可以使用指针将节点链接在一起形成一棵树。但是，为了支持您想要的操作，每个节点需要 3 个指针(父节点、左节点、右节点)
两种方式都可以正常工作，但数组实现更简单、速度更快，并且使用的内存更少。
预计到达时间:
不过，我应该指出，如果您使用指针，那么您可以使用不同种类的堆。 Fibonacci 堆可以让您在摊销常数时间内递减节点的值。不过，它有点复杂，而且实践起来很慢:https://en.wikipedia.org/wiki/Fibonacci_heap
关于algorithm - 是否有使用指针的堆或类堆结构，换句话说，节点不在数组中？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56198152/