python 如何使用数组索引预先排序遍历最小堆

yfwxisqw  于 2023-04-19  发布在  Python
关注(0)|答案(1)|浏览(110)

我创建了一个标准的最小堆类。我试图找出一种方法来索引在最小堆中的值在前序遍历格式。唯一的方法,我已经看到它做的是使用左和右指针。但“节点”在我的数组不是节点只是值。是否有可能做前序遍历最小堆数组使用索引?如果是这样,如何?

igetnqfo

igetnqfo1#

左/右链接是隐式可用的,因为索引处的值的左子项𝑖将在索引2 + 1处找到𝑖(如果在数组的大小内),并且右子项在索引2𝑖+ 2处找到。
所以你可以使用已知的前序算法,并使用这些公式来访问孩子。
例如,我们可以有这样的min heap:

_3_
    /   \
   6     4
  / \   /
10   9 5

...它将被编码在一个数组中,如下所示:

[3, 6, 4, 10, 9, 5]

前序遍历将是:

3 6 10 9 4 5

下面是一个在JavaScript中运行的示例实现:

function preorder(minheap, start) {
    if (start >= minheap.length) return; // all done
    console.log(minheap[start]);
    preorder(minheap, start * 2 + 1); // left child
    preorder(minheap, start * 2 + 2); // right child
}

// Example run:
const minheap = [3, 6, 4, 10, 9, 5];
preorder(minheap, 0);

相关问题