algorithm - 堆排序的目的是什么？

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之前。

那么什么是堆？

什么是堆？

请注意，在上一节中，我区分了“堆”和“表示堆的数组”。先说什么是堆，再说什么是代表堆的数组。

最大堆是一个二叉树，其节点上有值，它满足以下两个属性:

• 子节点上的值总是低于其父节点上的值；
• 这棵树几乎是完整的，从这个意义上说，树的所有分支的长度几乎相同，最长和最短的分支之间最多相差 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) 操作中，通过重复提取最大元素。

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