是否有一种方法可以使用Foldr或Foldl函数在SML中编写堆排序算法?

Question

我想知道是否有一种方法可以使用SML的Foldr或Foldl函数编写堆排序算法。我在网上找不到一个例子，我想知道是否有人能给我一些关于这件事的指导。我想用一个递归最小的高阶函数来实现排序算法。但是我不知道从哪里开始。

Answer 1

维基百科文章中描述的堆排序分为两个阶段。首先，它将数组重新排列成一个Max-heap，最大的项位于位置0，其余的项排列形成一个有效的堆。

下一步对堆进行排序，依次将最大的项与数组末尾的项交换，减少计数，并将新项筛选回堆中。花点时间看看维基百科页面上的GIF动画示例。

排序阶段是这样的:

last_item = array.Length - 1
while (last_item > 0)
{
    // move largest item to the end of the array
    // and replace with the item that was at the end
    swap(0, last_item)
    // decrease the count,
    // and sift the item down to its proper place
    --last_item
    sift_down(0, last_item)
}

操作完成后，数组按升序排列。

我不明白foldl或foldr在这里有什么帮助。