使用链表实现二叉堆

Question

可能的重复：
二进制最小堆的链表实现（操作遇到问题......）

问候，

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

Answer 1

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