堆排序算法详解：从大根堆构建到完整排序实现

堆排序算法详解：从大根堆构建到完整排序实现

引用

CSDN

1.

https://m.blog.csdn.net/2401_87517331/article/details/143777846

堆排序是一种基于堆数据结构的排序算法，其中大根堆是最常用的一种。本文将详细介绍大根堆的概念、构建方法以及堆排序的具体实现。

大根堆的概念

首先，我们来引入大根堆的概念，以便更好地理解其工作原理。在堆中，每个父节点都有左右两个孩子节点，类似于高中生物的遗传图谱。不同的是，在堆中，每个父节点只能生两个孩子。

那么，什么是大根堆呢？大根堆的特点是：最上面的元素最大，即对于任何一个父节点来说，父节点都要比它的左右孩子大。只有满足这个条件的堆，才被称为大根堆。

1.1 堆排序中父节点和左右孩子的下标

堆是如何从数组中构建的呢？我们可以通过下图来理解：

从图中可以看出，堆的最上方是数组的下标0。我们可以将堆暂时看作一个二维数组。第0行是0，第1行下标是1和2，第2行下标是3、4、5和6。按照这种描述将堆排成一维数组后，就得到了下方的数组。

1.2 父节点和左右孩子的位置关系

父节点和左右孩子的位置关系如下：

• 假设父节点在一维数组中的下标是i，那么左孩子的下标就是2*i+1。
• 右孩子和左孩子相邻，且比左孩子大一位，因此右孩子的下标是2*i+2。

1.3 局部大根堆的构建思路

了解了大根堆的概念后，我们尝试构建一个大根堆。这里有两种思路：

1. 从下标0开始构建大根堆
2. 从最后一个父节点开始构造大根堆

第一种方法会让问题变得越来越复杂，因为随着层数的递进，需要处理的父节点数会呈指数级上升。因此，我们选择从最后一个父节点开始构建。

1.4 构建局部大根堆

首先，我们需要知道最后一个父节点的位置。最后一个父节点的下标index是arr.size()/2-1。

构建局部大根堆的代码如下：

void make_big(vector<int>& arr, int start, int end)
{
    int now = start; // 传入一个父节点。
    int l = 2 * now + 1; // 找到左孩子
    for (; l <= end; now = l, l = 2 * now + 1)
    {
        if (l < end && arr[l] < arr[l + 1]) l++; // 如果这个节点有右孩子并且右孩子大的话
        if (arr[now] < arr[l])
        {
            swap(arr[now], arr[l]);
        }
        // 如果父亲小于孩子就交换 // 注意孩子也可能是一个父亲，所以对孩子也要判断一下。
        else { break; } // 局部大根堆构建完成
    }
}

这段代码中：

• start参数用于指定需要构造哪个位置的局部大根堆。
• end参数用于避免下标越界。
• 代码通过循环找到最大孩子，并与父节点进行比较和交换。

1.5 局部大根堆代码思路讲解

代码的具体思路如下：

1. 首先确定需要构造哪个位置的局部大根堆（父节点下标start）以及数组中一共有多少数（end）。
2. 找到两个孩子中较大的那个。
3. 如果父节点比孩子小，则进行交换，并继续检查孩子节点的大根堆是否成立。

2. 大根堆的实现和堆的排序思维

大根堆的完整实现代码如下：

int x = arr.size() / 2 - 1; // 找到最后一个父节点。
for (int i = x; i >= 0; i--)
{
    make_big(arr, i, arr.size() - 1);
}
int end = arr.size() - 1;
// 构造大根堆。
// 之后进行交换。

for (int i = 0; i < arr.size() - 1; i++)
{
    swap(arr[0], arr[end]);
    end--;
    make_big(arr, 0, end);
}

堆排序的核心思想是：

1. 首先构建一个大根堆，使得堆顶元素是当前堆中的最大值。
2. 将堆顶元素（最大值）与堆的最后一个元素交换，然后调整堆，使得剩余元素重新构成大根堆。
3. 重复上述过程，直到整个数组有序。

完整代码如下：

#include<iostream>
#include<vector>
using namespace std;

void make_big(vector<int>& arr, int start, int end)
{
    int now = start; // 传入一个父节点。
    int l = 2 * now + 1; // 找到左孩子
    for (; l <= end; now = l, l = 2 * now + 1)
    {
        if (l < end && arr[l] < arr[l + 1]) l++; // 如果这个节点有右孩子并且右孩子大的话
        if (arr[now] < arr[l])
        {
            swap(arr[now], arr[l]);
        }
        // 如果父亲小于孩子就交换 // 注意孩子也可能是一个父亲，所以对孩子也要判断一下。
        else { break; } // 局部大根堆构建完成
    }
}

void foster(vector<int>& arr)
{
    int x = arr.size() / 2 - 1; // 找到最后一个父节点。
    for (int i = x; i >= 0; i--)
    {
        make_big(arr, i, arr.size() - 1);
    }
    int end = arr.size() - 1;
    // 构造大根堆。
    // 之后进行交换。
    for (int i = 0; i < arr.size() - 1; i++)
    {
        swap(arr[0], arr[end]);
        end--;
        make_big(arr, 0, end);
    }
    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << ' ';
    }
}

int main()
{
    vector<int> arr = { 1, 4, 3, 7, 9, 8, 5 }; // 一共有7个数字。
    foster(arr);
}

通过这个案例代码，读者可以直观地看到堆排序算法的实现过程。如果对文章内容有任何疑问，欢迎在评论区留言讨论。