5

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

谢谢帮助

4

5 回答 5

2

A priority queue using a heap ordered binary tree can be implemented using a triply linked list structure instead of an array. you will need three links per node:two to traverse down and one to traverse up.

于 2012-10-13T04:40:28.440 回答
0

heapq 模块源码展示了实现上下推的步骤。要从数组实现切换到指针实现，请将arr[2*n+1]计算替换为node.left和。对于诸如 的父引用，每个节点都需要一个指向其父节点的指针。arr[2*n+2]node.rightarr[(n-1)>>1]node.parent

或者，您可以采用一种功能样式，这使得这一切都非常容易实现。我发现在 Lisp 中实现的 treaps代码是如何做到这一点的灵感。

于 2011-10-29T20:30:34.973 回答
0

作为很久以前的任务的一部分，我已经解决了这个问题。你可以在这里找到

我在 Java 和 C++ 中有多个实现，使用和不使用数组实现 MinHeap。有关解决方案，请参阅我的 Java 实现。是的，在没有数组的情况下实现堆是很有可能的。你只需要记住在哪里插入下一个节点以及如何堆和反向堆。

Edit1：我还尝试查找没有数组的最小堆的任何现有解决方案，但找不到任何解决方案。因此，我将其发布在这里，以便对任何希望了解该方法的人有所帮助。

于 2019-03-09T12:38:52.080 回答
-1

是的，您可以在不依赖数组的情况下实现它。我个人依赖二进制计数器......这是我在 c 中的实现（ https://github.com/mohamedadnane8/HeapsUsingPointers ）。请注意，这仍然是一个非常快速的 log(n) 实现。

                1 => binary "1"
            2=> "10"            3=> "11"
4=>  "100"      5= "101"     6="110"        7="111"

在这个程序中，我尝试使用数字序列来插入和删除，正如你在上面看到的那样，树可以很容易地表示为二进制数字字符串。二进制字符串中的第一个“1”是开始。之后，0 和 1 的顺序决定了去哪里，“1”表示向左，“0”表示向右。

另外，请注意，这个实现依赖于一个非常小的字符或整数数组，这使得二进制数的计算更快，但是你可以依赖 bin() 函数将你的计数器转换为二进制数（我实现了这个数组只是为了练习有点我解决问题的能力）。对不起，如果我不能很好地解释它，我的沟通能力有点欠缺。

于 2020-08-19T14:49:30.363 回答
-4

没有数组很难实现二进制堆。因为您应该在插入时保留所有父级，然后进行上下推操作。像那样[parent_1, parent_2 ... parant_k] and then if parent_(k+1) < parant_k pushUp重新排列他们的右孩子和左孩子

于 2011-01-15T06:46:01.687 回答