heap - 没有数组的 MinMax Heap 实现

Question

我发现了很多 MinMax Heap 实现，它们将数据存储在一个数组中。这真的很容易实现，这就是我正在寻找不同的东西的方式。我想创建一个 MinMax 堆，只使用堆的元素和指向左 child 和右 child 的指针(当然还有一个比较的键)。所以堆只有指向根对象的指针(最小级别)，而根对象有一个指向他的 child 的指针(最大级别)等等。我知道如何插入一个新对象(根据堆大小使用 int 的二进制表示找到正确的路径)，但我不知道如何实现其余的(上推(下推)元素，查找父级或祖父级) .

谢谢帮助

Answer 1

使用堆有序二叉树的优先级队列可以使用三链表结构而不是数组来实现。每个节点需要三个链接:两个向下遍历，一个向上遍历。