堆排序详解：大根堆的概念与实现

堆排序详解：大根堆的概念与实现

引用

CSDN

1.

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

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

大根堆的概念

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

那么，什么是大根堆呢？大根堆是一种特殊的堆结构，其特点是根节点的值最大，且对于堆中的任意父节点，其值都大于或等于其左右孩子的值。

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

堆实际上是从数组中构建而来的。通过观察堆的结构，我们可以发现：

• 第0行对应数组下标0
• 第1行对应数组下标1和2
• 第2行对应数组下标3、4、5和6

这种映射关系可以表示为：如果父节点在一维数组中的下标是i，那么其左孩子的下标为2i+1，右孩子的下标为2i+2。

1.2 局部大根堆的构建思路

在构建大根堆时，有两种主要思路：

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

从最后一个父节点开始构建大根堆更为高效，因为这样可以避免在构建过程中处理过多的父节点。

1.3 构建局部大根堆

要从最后一个父节点开始构建大根堆，首先需要确定最后一个父节点的位置。最后一个父节点的下标可以通过公式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; } // 局部大根堆构建完成
    }
}

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

这段代码的主要思路是：

1. 接受需要构造的父节点坐标start以及数组中元素的数量end
2. 找到两个孩子中较大的那个
3. 如果父节点小于孩子，则进行交换
4. 如果发生交换，则继续检查孩子的大根堆是否成立

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);
}

通过以上代码，可以实现对数组的堆排序。如果对文章内容有任何疑问，欢迎在评论区留言讨论。