数据结构——堆排序

悠悠 2023-06-23 13:16 32阅读 0赞

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

在之前的文章中已经介绍过大小顶堆的实现办法，再简单介绍一下。

### 大顶堆 ###

### ![format_png][] ###

### 小顶堆 ###

![format_png 1][]

## 堆排序 ##

堆排序（Heapsort）是指利用堆这种数据结构（后面的【图解数据结构】内容会讲解分析）所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

*  大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
 *  小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

## 算法步骤 ##

1.  创建一个堆 H\[0……n-1\]；
2.  把堆首（最大值）和堆尾互换；
3.  把堆的尺寸缩小 1，并调用 shift\_down(0)，目的是把新的数组顶端数据调整到相应位置；
4.  重复步骤 2，直到堆的尺寸为 1。

来源：[https://github.com/hustcc/JS-Sorting-Algorithm][https_github.com_hustcc_JS-Sorting-Algorithm]

## 算法演示 ##

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTljMzdiNGJlMWI3Yzk2ZDEuZ2lmP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvOTUwL2Zvcm1hdC93ZWJw][]

## 排序动画过程解释 ##

1.  首先，将所有的数字存储在堆中
2.  按大顶堆构建堆，其中大顶堆的一个特性是数据将被从大到小取出，将取出的数字按照相反的顺序进行排列，数字就完成了排序
3.  在这里数字 5 先入堆
4.  数字 2 入堆
5.  数字 7 入堆， 7 此时是最后一个节点，与最后一个非叶子节点（也就是数字 5 ）进行比较，由于 7 大于 5 ，所以 7 和 5 交互
6.  按照上述的操作将所有数字入堆，然后从左到右，从上到下进行调整，构造出大顶堆
7.  入堆完成之后，将堆顶元素取出，将末尾元素置于堆顶，重新调整结构，使其满足堆定义
8.  堆顶元素数字 7 取出，末尾元素数字 4 置于堆顶，为了维护好大顶堆的定义，最后一个非叶子节点数字 5 与 4 比较，而后交换两个数字的位置
9.  反复执行调整+交换步骤，直到整个序列有序

## 代码实现 ##

/* 
     * (最大)堆的向下调整算法
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *     其中，N为数组下标索引值，如数组中第1个数对应的N为0。
     *
     * 参数说明：
     *     a -- 待排序的数组
     *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     *     end   -- 截至范围(一般为数组中最后一个元素的索引)
     */
    void maxheap_down(int a[], int start, int end)
    {
        int c = start;            // 当前(current)节点的位置
        int l = 2*c + 1;        // 左(left)孩子的位置
        int tmp = a[c];            // 当前(current)节点的大小
        for (; l <= end; c=l,l=2*l+1)
        {
            // "l"是左孩子，"l+1"是右孩子
            if ( l < end && a[l] < a[l+1])
                l++;        // 左右两孩子中选择较大者，即m_heap[l+1]
            if (tmp >= a[l])
                break;        // 调整结束
            else            // 交换值
            {
                a[c] = a[l];
                a[l]= tmp;
            }
        }
    }
    
    /*
     * 堆排序(从小到大)
     *
     * 参数说明：
     *     a -- 待排序的数组
     *     n -- 数组的长度
     */
    void heap_sort_asc(int a[], int n)
    {
        int i;
    
        // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
        for (i = n / 2 - 1; i >= 0; i--)
            maxheap_down(a, i, n-1);
    
        // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
        for (i = n - 1; i > 0; i--)
        {
            // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
            swap(a[0], a[i]);
            // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
            // 即，保证a[i-1]是a[0...i-1]中的最大值。
            maxheap_down(a, 0, i-1);
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTU4YWJkNmE5ODQ0MGZiZGUucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvNzc2L2Zvcm1hdC93ZWJw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTQ4YjYyMmEzZDE5MTM0MDcucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvODEwL2Zvcm1hdC93ZWJw?x-oss-process=image/format,png
[https_github.com_hustcc_JS-Sorting-Algorithm]: https://github.com/hustcc/JS-Sorting-Algorithm
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTljMzdiNGJlMWI3Yzk2ZDEuZ2lmP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvOTUwL2Zvcm1hdC93ZWJw]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTljMzdiNGJlMWI3Yzk2ZDEuZ2lmP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvOTUwL2Zvcm1hdC93ZWJw