数据结构和算法学习之路——堆排序(C++)_用筛选法将该序列构建小顶堆,并将最小元素输出后的剩余元素调整为堆,以完全二叉树

数据结构和算法学习之路——堆排序(C++)

You cannot improve your past, but you can improve your future. Once time is wasted, life is wasted.
——你不能改变你的过去，但你可以让你的未来变得更美好。一旦时间浪费了，生命就浪费了。

堆排序是利用堆的性质进行的一种选择排序，它只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间

1. 什么是堆？

在进行堆排序的学习之前，我们得先了解一下什么是堆？
堆 heap 是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

1. 堆中某个节点的值总是不大于或不小于其父节点的值；
2. 堆得是完全二叉树；

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

2.堆排序的过程

我们以小顶堆为例，那么我们第一个应该输出的就是堆顶的最小值了，接下来把剩余的n-1个元素序列重新组建成一个堆，再得到原序列的次小值，重复上述过程，最后得到一个有序的序列，这个过程称为堆排序

好的，让我们开始吧
首先以下面这个序列为例进行堆排序：

{49, 38, 65, 97, 76, 13, 27, 55}
1

第一步，我们得先构建一个完全二叉树（构建的方法：自顶向下，从左往右地构建）

当然，这并不是堆，因为它不满足堆的第一个要求，我们现在就要开始对它做一些调整使他变成一个小顶堆。

第二步：用筛选法建立小顶堆
我们来看看筛选法的步骤：

1. 首先将N个数据元素存入一个一维数组，并把这个数组视作一棵完全二叉树。（我们在第一步已经实现）
2. 从二叉树的最后一个非叶结点开始用从上向下过滤的方法调整以该非叶结点为根节点的二叉树为小顶堆
3. 对前面的结点依次执行2的操作直到根结点执行完成为止。此时这棵二叉树就调整为了一个小顶堆

我们来看看图示流程，（手画的，有些简陋）

因此，我们得到的小顶堆的序列就是：

{13, 38, 27, 55, 76, 65, 49, 97}
1

第三步：
把堆顶（最小的元素）输出，然后把剩下的部分再次构成堆
在本例中，我们把13输出之后，只需要用堆中最后一个元素代替它，然后，对剩余的部分自顶向下调整即可
下面，我们看看输出完13之后我们是怎么调整的：
（我们用蓝色字迹的笔表示已经输出的结点，也就是说新堆的调整不用管它了）

第四步：重复第三步，把27输出，然后继续调整堆
第五步：…

怎么样，其实堆排序的思路也是很清晰的，只是我们需要用到堆这样的数据结构罢了

3. 堆排序的C++实现

下面就是代码实现环节了，整个堆排序应该包括两个步骤：

1. 构建小顶堆（大顶堆也行，在本例中我们就以小顶堆为例，方法类似）
2. 调整堆

在给出代码之前，有几点是要提前说明的：

1. 由于堆通常是一个可以被看做一棵树的数组对象，所以我们使用数组就可以描述堆
2. 在堆中（或者说数组形式的堆中），只有下标为N / 2 -1 以及之前的元素才会有子结点（N代表数组长度）
3. 若我们已知下标为X的元素它有子结点，那么2X + 1表示它的左孩子的下标，2X + 2表示它的右孩子的下标

在了解了这些性质之后，我们看代码就能更好的理解了
下面这个是对堆进行调整的代码：

void minheap_down(int a[], int start, int end)
{
    int c = start;
    int left = 2*c + 1; //左孩子的位置
    int temp = a[c];
    for (; left <= end; c = left, left = 2*left + 1)
    {
        if (left < end && a[left] > a[left+1])
        {
            left ++;        // 左右两孩子中选择较小者，把left作为其下标
        }
        if(temp <= a[left])
        {
            break;    //如果父结点比子结点中最小的值还要小，那么无需交换
        }
        else
        {
            a[c] = a[left];
            a[left] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

下面这个是堆排序操作代码：

void heap_sort_asc(int a[], int n)
{
    int i,tmp;
    for(i = n/2 -1; i >= 0; i--)   //因为只有下标为n / 2 -1 以及之前的元素才会有子结点，所以我们从这个下标开始，往前走
    {
        minheap_down(a, i, n - 1);
    }
    for (i = n - 1; i > 0; i--)
    {
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        minheap_down(a, 0, i-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14