是按“默认”排序的最小堆。

Question

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

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

构建的最小堆可以从左到右，从上到下(从根到叶，按级别)读取，然后排序。

这是min堆的属性，还是我无法得到此属性不适用的情况。麦克斯·堆不是这样工作的，至少我在这里得到的东西是这样的。

输出：

2345 7 34 6 3 5 4 5 1 2 2 2 1 3 3 3 2 1

1 1 1 2 2 2 3 3 3 4 5 5 6 7 34 2345

谢谢您的回复！

Answer 1

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

要对构建的堆进行排序，您必须打印第一个元素(这是所有堆中最好的元素，根据您定义的比较器，min、max等)，然后您必须用最后一个元素“覆盖”第一个元素并删除最后一个元素，然后必须对第一个元素应用sift以使其在堆中的位置正确。然后重复，直到堆中没有剩下的元素