java - 使用链表实现二叉堆

Question

可能重复：
Binary Min Heap 的链表实现（操作有问题……）

问候，

我无法找出一种算法，该算法将为我提供二叉堆的链表实现中树节点的位置。我已经使用数组实现了一个堆，现在我想尝试使用链表；如果我使用数组来表示堆，有没有办法找到其数组索引的树节点？

score 5 · Accepted Answer

重点是什么？链表实现将比基于数组的实现更慢或更复杂。如果你用一个简单的链表替换数组并且不添加其他结构，你的插入时间将是 O(n) 而不是 O(log n)，那么你也可以在相同的 O(n ) 复杂性。

score 0 · Accepted Answer

0

于 2011-04-10T05:03:51.977 回答

2 回答 2