堆排序的作用是什么？建堆已排列元素为何还要使用堆排序？

你对build_heap的作用存在错误认知：建堆操作并不会将数组排列为全局升序或者降序，它只是让数组满足堆的局部约束：

• 最大堆仅要求每个父节点的取值大于等于它的所有子节点
• 最小堆仅要求每个父节点的取值小于等于它的所有子节点

举个直观的例子：输入数组[3,1,2,5,4]，调用最大堆的build_heap之后，得到的数组是[5,4,2,1,3]，这个数组明显不是全局有序的，只是符合最大堆的父子节点约束，只能保证根节点（下标0位置）是整个数组的最大值，其余位置没有全局顺序要求。

你提供的代码已经可以清晰看出两者的定位差异：

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

build_heap的时间复杂度是O(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);
    }
}

堆排序是在build_heap的基础上，额外执行了O(nlogn)的迭代操作：每次把当前堆的根节点（当前堆的最大值）交换到堆末尾的有序区，再缩小堆范围重新调整堆结构，最终才能得到全局升序的数组，适合需要全量有序结果的场景。

简单来说：建堆是堆排序的前置步骤，它本身不完成排序功能，堆排序的价值就是把只有局部有序性的堆，转换为全局有序的数组。

内容的提问来源于stack exchange，提问作者Akhil S R