algorithm - d-heap 如何在 O(log n) 中执行插入和删除？

Question

我正在研究优先队列和 d-heap 来实现这个数据结构。我找到了这个数据类型定义:

class DHeap implements PriorityQueue:
data:
a d-heap T containing n nodes; each node contains an element (elem) and a key (key) taken from an ordered universe.
operations:
findMin() -> elem T(n) = O(1)
insert(elem e, key k) T(n) = O(log n)
creates a new node v with element e and key k, makes it a leaf of T and restore the ordering rules.
delete(elem e) T(n) = O(d * log n)
exchanges the node v containing the element with any leaf u on the last level of T, then deletes v and restores the ordering rule pushing the node u to its correct position.
decreaseKey(elem e, key d) T(n) = O(log n)
increaseKey(elem e, key d) T(n) = O(d * log n)

我省略了操作的全部细节，因为我的问题集中在 delete 如何在 d*log n 中执行删除并在 log n 中插入。

我知道 d - 1 是在路径根叶节点的子节点之间寻找更小或更大节点键的时间，log n 是树的高度，所以 d*log n 是成本最坏情况下的比较。但是，如何在 d*log n 中找到包含元素的节点？我认为这个操作需要 O(n)(访问堆的时间)并且操作成本忽略了这个细节。我错了吗？

另一个问题是:如何在基于链接的树中插入一个节点作为叶子？我需要一些指向缺失叶子的指示吗？但是我该如何处理释放位置的删除？

希望得到回复，谢谢。

Answer 1

But, how can i find the node that contains an element in d*log n? I think that this operation requires O(n) (time to visit the heap) and the operation cost ignores that detail. Am i wrong?

为了高效实现，您需要一个辅助数据结构来存储从元素到节点的映射。

Another question is: how can i insert a node as leaf in a linked-based tree? Do I need some pointers to missing leafs? But how can i handle the deletions that releases positions?

简单的答案是使用数组，就像在二叉堆中一样。或者，您可以 扩充堆节点以指向它们最左边的空子节点，这样找到下一个叶节点的时间就是 O(log_d n)。 维护一个指向下一个叶节点的指针，从而保持完整需要的d叉树结构。