1

我刚刚学习了“算法简介”，并开始在 c# 中实现堆和堆排序算法。

实现一个从双精度数组构造最小/最大堆的函数，我注意到构造的堆具有一些有趣的属性。

构建的最小堆可以从左到右，从上到下（从根到叶，按级别）读取，并将对其进行排序。

这是 minheap 的属性，还是我无法获得此属性不适用的情况。最大堆不能以这种方式工作，至少我在这里得到了什么。

输出：

2345 7 34 6 3 5 4 5 1 2 3 2 1 3 1 3 2 1（最大堆）

1 1 1 1 2 2 2 3 3 3 3 4 5 5 6 7 34 2345（最小堆）

感谢您提前回复！

4

2 回答 2

5

堆只在父节点和它们各自的子节点之间有关系。同一级别的节点之间没有关系。

For Min Heaps: Value of Parent node <= Value of its child nodes
For Max Heaps: Value of Parent node >= Value of its child nodes

因此，当从上到下、从左到右移动时，不需要对 Min Heap 进行排序。在你的情况下，这只是一个巧合。
例如：考虑这个序列： 这些是 MinHeapify 顺序，但显然 不是排序顺序。 访问这个Interactive Heap Link或这个链接以获得关于如何构建堆的正确可视化。1, 3, 2, 5, 4, 10, 9 上述序列的堆

于 2015-08-11T19:43:19.293 回答
0

为了使堆的实现更加健壮，人们通常将您可以对节点进行的两个操作称为：sift和percolate

sift通过用你找到的两个儿子中最好的一个来切换节点，尽可能地将节点放在树上。

有可能执行该sift程序

 public void sift (int i)
    {
        while (i != 0)
        {
            if (compare(heapData[i], parentValue(i)))
            {
                switchValuesAtIndexes(parentIndex(i), i);
                i = parentIndex(i);
            }
            else
                break;
        }
    }

percolate通过与父节点切换节点，将节点尽可能地放在树上。

public void percolate (int i)
    {
        while (true)
        {
            if (indexExists(leftIndex(i)) && (!indexExists(rightIndex(i)) && compare(leftValue(i), heapData[i]) || indexExists(rightIndex(i)) && compare(leftValue(i), rightValue(i)) && compare (leftValue (i), heapData[i])))
            {
                switchValuesAtIndexes(leftIndex(i), i);
                i = leftIndex(i);
            }
            else
                if (indexExists(rightIndex(i)) && (compare (rightValue(i), leftValue(i)) && compare (rightValue(i), heapData[i])))
                {
                    switchValuesAtIndexes(rightIndex(i), i);
                    i = rightIndex(i);
                }
            else
                break;
        }
    }

要构建堆，您需要对数组的每个元素应用sift或（或两者）percolate

要对您构建的堆进行排序，您必须打印第一个元素（这是与您定义的比较器、最小值、最大值等相关的所有堆中最好的）然后您必须用最后一个“覆盖”第一个元素并删除最后一个，然后您必须应用sift第一个元素以将其带到堆中的正确位置。然后重复直到堆中没有元素

于 2015-08-12T07:47:41.637 回答