2

使用堆排序按降序排序并显示步骤或解释请在下面是树

                             79
                       33           57
                    8     25    48

下面是数组 79 - 33 - 57 - 8 - 25 - 48 ok 升序很容易，因为最大的元素在顶部，我们可以交换最后一个元素和第一个元素，然后使用 heapify 作为 wikipedia 中的示例代码描述它。

好的，让我澄清一下，堆是建立在我画的树上的。我知道升序的步骤，数组看起来像 8 - 25 - 33 - 48 - 57 - 79。但是降序的步骤是什么。这是一个非常直接的问题。只需解释按降序排列数组所需的步骤。

4

1 回答 1

2

这看起来像一个最大堆，所以按降序排序很简单：

FUNCTION descSortedFrom(Heap h) : Array

   LET N := h.size
   LET ret := NEW Array (size = N)

   FOR i = 0..N-1 DO
      ret[i] := h.deleteMax

   RETURN ret

二叉堆、二项式堆和斐波那契堆都支持 中的最大堆上的 deleteMax（或类似地，最小堆上的 deleteMin）O(log N)，所以总的来说这是O(N log N)，这对于基于比较的排序是最佳的。

请注意，为简单起见，这使用了外部存储阵列。如果您坚持使用与堆相同的数组，那么只需像您所做的那样进行升序排序，然后（猜猜是什么？）反转数组O(N)。

替代解决方案

这比必要的复杂，但是一次性和就地。本质上，不是将数组元素[0..k)视为堆元素，[N-k..N)而是取而代之。您必须修改heapify以获取起始偏移量以适应此更改。

为了说明，正如您所知道的，这是您按升序排序的方式：

entire array = [ the heap elements ; the sorted asc elements ]

本质上，您从右到左构建排序的 asc 元素，将堆的第一个元素（它的最大值）与堆的最后一个元素交换，将堆大小缩小一个，然后堆化剩余的堆元素。

按降序排序在概念上是相同的：

entire array = [ the sorted desc elements ; the heap elements ]

您从左到右构建排序的 desc 元素。不需要重新定位堆的最大值，您只需将堆大小缩小一，但不是在尾部截断，而是在头部截断。因此，您必须提供一个 offset 参数，heapify以便它知道堆元素在数组中实际开始的位置。

于 2010-06-01T04:45:38.353 回答