数据结构与算法系列之一：八大排序之堆排序

雨点打透心脏的1/2处 2022-06-02 08:56 201阅读 0赞

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **个人博客：[https://wordzzzz.github.io/][https_wordzzzz.github.io] && [https://wordzzzz.gitee.io/][https_wordzzzz.gitee.io]**
 *  **代码地址：[https://github.com/WordZzzz/Note/tree/master/DS-A][https_github.com_WordZzzz_Note_tree_master_DS-A]**
 *  **博客作者：WordZzzz，一只热爱技术的文艺青年**

--------------------

*   *  堆排序
        
         *  前言
         *  简介
         *  步骤
         *  演示
         *  代码
            
             *  递归版
             *  迭代版
         *  算法复杂度
         *  分析

## 堆排序 ##

### 前言 ###

建议先看排序综述，传送门：[数据结构与算法系列之一：八大排序综述][Link 1]。

### 简介 ###

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

*  父节点i的左子节点在位置 (2i\+1)。
 *  父节点i的右子节点在位置 (2i\+2)。
 *  子节点i的父节点在位置 floor((i−1)/2)。

在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

*  最大堆调整（Max\_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
 *  创建最大堆（Build\_Max\_Heap）：将堆所有数据重新排序。
 *  堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

### 步骤 ###

基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del\_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。堆排序的过程是：

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

### 演示 ###

wikipedia的大数据规模演示：

![heapsort from wikipedia][]

### 代码 ###

#### 递归版 ####

/*
    * 堆排序递归版
    */
    
    template <typename T>
    void MaxHeapifyRecursive(T *array, int i, int heapSize) {
        int sonl = 2 * i + 1;
        int sonr = 2 * i + 2;
        int dad = i;
        if (sonl <= heapSize && array[sonl]>array[i]){                  //如果左子结点大于父结点，则父结点指向子结点
            dad = sonl;
        }
        if (sonr <= heapSize && array[sonr]>array[dad]){                //如果右子结点大于父结点，则父结点指向子结点
            dad = sonr;
        }
        if (dad != i){                                                  //如果dad != i则说明父结点不是最大值，交换后递归执行MaxHeapifyRecursive
            swap(array[i], array[dad]);
            MaxHeapifyRecursive(array, dad, heapSize);
        }
    }
    
    template <typename T>
    void HeapSort(T *array, const int length) {
        if (array == NULL)
            throw invalid_argument("Array must not be empty");
        if (length <= 0)
            return;
    
        //初始化，i从最后一个父结点开始调整
        for (int i = length / 2 - 1; i >= 0; --i){
            //构建最大堆 
            MaxHeapifyRecursive(array, i, length - 1);
    //      MaxHeapifyIteration(array, i, length - 1);
        }
        //先将第一个元素和已经排好的元素前一位做交换，再从新调整（刚调整的元素之前的元素），直到排序完毕
        for (int i = length - 1; i >= 0; --i){
            swap(array[0], array[i]);
            MaxHeapifyRecursive(array, 0, i - 1);
    //      MaxHeapifyIteration(array, 0, i - 1);
        }
    }

#### 迭代版 ####

/*
    * 堆排序迭代版
    */
    
    template <typename T>
    void MaxHeapifyIteration(T *array, int left, int right) {
        //建立父结点指针和子结点指针
        int dad = left;
        int son = dad * 2 + 1;
        while (son <= right) {                                          //若子结点指针在范围内才做比较
            if (son + 1 <= right && array[son] < array[son + 1])        //先比较两个子结点的大小，选择最大的
                son++;
            if (array[dad] > array[son])                                //如果父结点大于子结点代表调整完毕，直接跳出循环
                return;
            else {                                                      //否则交换父子内容在继续子结点和孙结点的比较
                swap(array[dad], array[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    
    template <typename T>
    void HeapSort(T *array, const int length) {
        if (array == NULL)
            throw invalid_argument("Array must not be empty");
        if (length <= 0)
            return;
    
        //初始化，i从最后一个父结点开始调整
        for (int i = length / 2 - 1; i >= 0; --i){
            //构建最大堆 
    //      MaxHeapifyRecursive(array, i, length - 1);
            MaxHeapifyIteration(array, i, length - 1);
        }
        //先将第一个元素和已经排好的元素前一位做交换，再从新调整（刚调整的元素之前的元素），直到排序完毕
        for (int i = length - 1; i >= 0; --i){
            swap(array[0], array[i]);
    //      MaxHeapifyRecursive(array, 0, i - 1);
            MaxHeapifyIteration(array, 0, i - 1);
        }
    }

### 算法复杂度 ###

*  数据结构 数组
 *  最坏时间复杂度 O(nlogn)
 *  最优时间复杂度 O(nlogn)
 *  平均时间复杂度 O(nlogn)
 *  空间复杂度 O(n) total, O(1) auxiliary

### 分析 ###

原地堆排序已经是空间优化版本了，因为它不再需要申请额外的空间。

整个算法的过程分为建堆和排序两个过程，首先对现有数组建立最大堆，然后一边提取堆顶的最大值，一边减小堆的尺寸，最后堆尺寸为1时，排序也就完成了。如果大家对整个算法的执行过程不太了解，可以看一下下面这两张图，第一张是建堆的过程示意图，第二张是排序的过程示意图。图片来自：[http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/][http_bubkoo.com_2014_01_14_sort-algorithm_heap-sort]

![bubblesort from wordzzzz][]

![bubblesort from wordzzzz][bubblesort from wordzzzz 1]

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_wordzzzz.github.io]: https://wordzzzz.github.io/
[https_wordzzzz.gitee.io]: https://wordzzzz.gitee.io/
[https_github.com_WordZzzz_Note_tree_master_DS-A]: https://github.com/WordZzzz/Note/tree/master/DS-A
[Link 1]: http://blog.csdn.net/u011475210/article/details/79014021
[heapsort from wikipedia]: /images/20220602/e807a14a22e94870b80ed846233566ed.png
[http_bubkoo.com_2014_01_14_sort-algorithm_heap-sort]: http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
[bubblesort from wordzzzz]: /images/20220602/42f91de46a644d0abb6fd335c71c695a.png
[bubblesort from wordzzzz 1]: /images/20220602/19a1f75ff8454055a9735f779e3927b8.png