堆排序（数据结构）

╰半橙微兮° 2024-04-23 20:13 9阅读 0赞

![在这里插入图片描述][daa4d9c510194961871c0ba2aabf1789.png]

#### 堆排序 ####

![在这里插入图片描述][2fff96ee448f4bf5aaa0f92d468f5c14.png]

##### 建立大根堆 #####

![在这里插入图片描述][0701396f018047c98fcbb64717ec5a8b.png]  
![在这里插入图片描述][6e614f9657a6460398a10cc18242ef33.png]

##### 大根堆代码实现 #####

/**
     * 大根堆：根 >= 左、右
     * 注意：基于【大根堆】的排序得到的序列是【递增序列】
     * @file HeapSort_Max.cpp
     */
    
    #include <stdlib.h>
    
    using namespace std;
    
    // 建立大根堆
    void BuildMaxHeap(int arr[], int len);
    
    // 将元素k为根的子树进行调整
    void MaxHeapAdjust(int arr[], int k, int len);
    
    // 堆排序
    void HeapSort_Max(int arr[], int len);
    
    // 交换元素
    void Swap1(int &a, int &b);
    
    
    
    void BuildMaxHeap(int arr[], int len) {
        
        // 检查所有的非叶子结点，看是否满足大根堆的要求，反复调整堆
        for(int i = len/2;i > 0;i--) {
        
            MaxHeapAdjust(arr, i, len);
        }
    }
    
    void MaxHeapAdjust(int arr[], int k, int len) {
        
        arr[0] = arr[k]; // arr[0]暂存子树的根节点
        for(int i = 2*k;i <= len;i *= 2) {
        
            // 左孩子 < 右孩子
            if(i < len && arr[i] < arr[i+1]) {
        
                i++;
            }
            if(arr[0] > arr[i]) {
         // 双亲结点大，筛选结束
                break;
            } else {
        
                arr[k] = arr[i]; // 将较大的孩子结点调整到双亲结点
                k = i;
            }
        }
        arr[k] = arr[0];
    }
    
    void HeapSort_Max(int arr[], int len) {
        
        BuildMaxHeap(arr, len); // 初始建立大根堆
        for(int i = len;i > 1;i--) {
        
            // arr[0]不存元素,arr[1]是堆顶元素,每交换一次都相当于把大的元素放到数组后面
            Swap1(arr[i],arr[1]);
            // 交换后，把剩余i-1个元素整理成堆
            MaxHeapAdjust(arr, 1, i-1);
        }
    }
    
    void Swap1(int &a, int &b) {
        
        int temp = a;
        a = b;
        b = temp;
    }

##### 小根堆代码实现 #####

/**
     * 小根堆：根 <= 左、右
     * 注意：基于【小根堆】的排序得到的序列是【递减序列】
     * @file HeapSort_Min.cpp
     */
    
    #include <stdlib.h>
    
    using namespace std;
    
    // 建立小根堆
    void BuildMinHeap(int arr[], int len);
    
    // 将元素k为根的子树进行调整
    void MinHeapAdjust(int arr[], int k, int len);
    
    // 堆排序
    void HeapSort_Min(int arr[], int len);
    
    // 交换元素
    void Swap2(int &a, int &b);
    
    
    
    void BuildMinHeap(int arr[], int len) {
        
        // 检查所有的非叶子结点，调整为小根堆
        for(int i = len/2;i > 0;i--) {
        
            MinHeapAdjust(arr, i, len);
        }
    }
    
    void MinHeapAdjust(int arr[], int k, int len) {
        
        // 将以k为根节点的子树调整为小根堆
        arr[0] = arr[k];
        for(int i = 2*k; i <= len; i*=2) {
        
            // 寻找左、右孩子中较小的结点
            if(i < len && arr[i] > arr[i+1]) {
        
                i++;
            }
            if(arr[0] <= arr[i]) {
        
                break; // 不用调整，结束
            } else {
        
                arr[k] = arr[i];
                k = i;
            }
        }
        arr[k] = arr[0];// 将被筛选的结点放入最终位置
    }
    
    void HeapSort_Min(int arr[], int len) {
        
        BuildMinHeap(arr, len);// 初始建立小根堆
        for(int i = len; i > 1;i--) {
        
            Swap2(arr[i], arr[1]);
            MinHeapAdjust(arr, 1, i-1);
        }
    }
    
    void Swap2(int &a, int &b) {
        
        int temp = a;
        a = b;
        b = temp;
    }

##### main函数 #####

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    #include "HeapSort_Max.cpp"
    #include "HeapSort_Min.cpp"
    
    using namespace std;
    
    /**
     * 使用当前时钟作为随机数种子:
     * rand() 产生的随机数在每次运行的时候都是与上一次相同的。若要不同, 
     * 用函数 srand() 初始化它。可以利用 srand((unsigned int)(time(NULL)) 的方法，
     * 产生不同的随机数种子，因为每一次运行程序的时间是不同的。
     */
    int main() {
        
        // 要取得 [a,b] 的随机整数，使用 (rand() % (b-a+1))+ a;
        int arr[10];
        int a = 1,b = 200;
        srand((unsigned)time(NULL)); 
        for(int i = 1;i <= 10;i++) {
        
            arr[i] = (rand() % (b-a+1))+ a;
        }
        cout << "原序列：";
        for(int i = 1;i <= 10;i++) {
        
            cout << arr[i] << " ";
        }
        cout << endl;
    
        // HeapSort_Max(arr, 10);
        HeapSort_Min(arr, 10);
        cout << "排序后：";
        for(int i = 1;i <= 10;i++) {
        
            cout << arr[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

#### 堆排序的效率分析 ####

![在这里插入图片描述][1df7634adca74da3ba84fff47d388431.png]  
![在这里插入图片描述][dda9b9f78b4748eaa37f305f2970a5fb.png]  
![在这里插入图片描述][b9a6cd897da6492f876b357667b33ba2.png]

#### 堆的插入和删除 ####

![在这里插入图片描述][ae8b46cba870419282ea10884b5f4758.png]

> 注：以上图片来自B站王道数据结构截图

[daa4d9c510194961871c0ba2aabf1789.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/57e6ded0ee3f4c8ca8c8fdf6384b5c72.png
[2fff96ee448f4bf5aaa0f92d468f5c14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c676567726864ceea4ea95ea45a3a4ff.png
[0701396f018047c98fcbb64717ec5a8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d1bb8a0ebcec41ceb8cc95bef41d125b.png
[6e614f9657a6460398a10cc18242ef33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5f200ecba7dc4a48b35316e86c1ffb9d.png
[1df7634adca74da3ba84fff47d388431.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5540a3fb09b646f898801d994f97d87c.png
[dda9b9f78b4748eaa37f305f2970a5fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f5943d0a1d2a4565aa226d5014d51435.png
[b9a6cd897da6492f876b357667b33ba2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/77ddfd67210a4d7d87805f444920a0f4.png
[ae8b46cba870419282ea10884b5f4758.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/017e5a99bbb4474b92da532d83ccf86b.png