堆排序的目的是什么？

Question

当我们构建堆时，数组中的元素会按照特定的顺序(升序或降序)排列，这取决于它是最大堆还是最小堆。那么，当构建堆本身以较低的时间复杂度按排序顺序排列元素时，堆排序的用途是什么？

    void build_heap (int Arr[ ])
        {
           for(int i = N/2-1 ; i >= 0; i-- )
           {
              down_heapify (Arr, i, N);
           }
        }

    void heap_sort(int Arr[], int N)
    {
        build_heap(Arr);
        
        for(int i = N-1; i >= 1; i--)
        {
            swap(Arr[i], Arr[0]);
            down_heapify(Arr, 0, i+1);
        }
    }

Answer 1

汇总堆排序

堆排序是一个算法，可以分为两个步骤：

• 将输入数组转换为堆；
• 将堆转换为排序数组。

堆本身是，而不是排序数组。

让我们看一个例子：

[9, 7, 3, 5, 4, 2, 0, 6, 8, 1]   # unsorted array

convert into heap
[9, 8, 3, 7, 4, 2, 0, 6, 5, 1]   # array representing a max-heap

sort
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]   # sorted array

如果仔细观察，您会注意到我的示例中的第二个数组(表示堆)没有完全排序。元素的顺序看起来比原始的未排序数组的随机性要小；它们看起来几乎是按递减顺序排序的；但是它们没有完全排序。数组中，3先于7，0先于6。

那么什么是堆呢？

什么是堆？

注意，在上一节中，我对“堆”和“表示堆的数组”进行了区分。让我们先讨论什么是堆，然后讨论什么是代表堆的数组。

max-堆是一个具有节点值的二叉树，它满足以下两个属性：

• 子节点上的值总是低于其父节点上的值；
• 树几乎是完全的，意思是树的所有分支几乎都有相同的长度，最长和短的分支之间最多相差1；此外，最长的分支必须在左边，最短的分支必须在右边。

在我给出的例子中，构建的堆是这样一个：

          9
      /      \
     8        3
   /   \     / \
  7     4   2   0
 / \   / \ / \ / \
6   5 1

您可以检查此二叉树是否满足堆的两个属性:每个子树的值都低于其父树，并且所有分支的长度几乎相同，每个分支总是有4个或3个值，最长的分支位于左侧，最短的分支位于右侧。

什么是代表堆的数组？

将二叉树存储到数组中通常很不方便，而且二叉树通常使用指针来实现，有点像链接列表。但是，堆是一个非常特殊的二叉树，它的“几乎完全”属性对于将其实现为数组非常有用。

我们所要做的就是读取每行从左到右的值行。在上面的堆中，我们有四行：

9
8 3
7 4 2 0
6 5 1

我们只需将这些值按该顺序存储在一个数组中：

[9,  8, 3,  7, 4, 2, 0,  6, 5, 1]

请注意，这正是我的文章开头的堆排序的第一步之后的数组。

在这种数组表示中，我们可以使用位置来确定哪个节点是哪个节点的子节点：i位置的节点有两个子节点，分别位于2*i+1和2*i+2位置。

这个数组是而不是排序数组。但是它表示一个堆，我们可以通过反复提取最大元素，轻松地使用它在n个log(n)操作中生成一个排序数组。

如果堆排序是用外部二叉树实现的，那么我们可以使用最大堆或最小堆，并通过反复选择最大元素或最小元素对数组进行排序。但是，如果您尝试就地实现堆排序，将堆存储为正在排序的数组中的数组，您会注意到使用max堆比使用min堆方便得多，以便通过反复选择max元素并将其移动到数组的末尾，从而对元素进行排序。