最小堆是否按 "default" 排序

Question

刚学会"Introduction to algorithms"，开始用c#实现堆和heapsort算法

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

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

这是一个属性的 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（最小堆）

提前感谢您的回复！

Answer 1

堆只有父节点和它们各自的子节点之间的关系。同级节点之间无关联

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

所以当从上到下，从左到右移动时，最小堆不需要排序。你的情况纯属巧合
例如：考虑这个序列：1, 3, 2, 5, 4, 10, 9
这些按 MinHeapify 顺序排列，但显然不是排序顺序。
访问此 Interactive Heap Link or this link 以正确可视化堆的构建方式。

Answer 2

为了使堆的实现更加健壮，人们通常将可以对节点进行的两个操作称为：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（或两者）

要对您构建的堆进行排序，您必须打印第一个元素（根据您定义的比较器、最小值、最大值等，这是所有堆中最好的元素）然后你将不得不 "overwrite" 第一个元素与最后一个元素并删除最后一个元素，然后你必须对第一个元素应用 sift 以将它带到堆中的正确位置。然后你重复直到堆中没有剩余元素

最小堆是否按 "default" 排序

Is minimum heap sorted by "default"

c#

sorting

algorithm

heap

min-heap