堆排序

堆的定义

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

大顶堆与小顶堆.png

堆的底层实现

• 堆使用一个一维数组表示；对堆中的元素进行编号，存入一维数组，如下图所示：

一维数组表示堆.png

• 对于性质（1）和（2）用数学表达式表示为：
  （1）大顶堆：
  （2）小顶堆：

堆排序

• 堆排序时间复杂度：O(nlogn)
• 堆排序基本思想： 将待排序序列构造成大顶堆，此时整个序列的最大值就在堆顶的根结点；将堆顶元素与末尾元素进行交换，此时末尾元素变成最大值；将剩余的n-1元素重新调整成大顶堆，如此循环下去，就得到一个从小到大排序的序列。
• 堆的重要性质：
  （1）第i个结点的左孩子为2i+1，右孩子为2i+2；
  （2）第i个结点的父结点为(i-1)/2；
  （2）堆中最后一个非叶子结点(n-2)/2，即为堆中最后一个结点n-1的父结点；

堆排序代码实现

1. 构造大顶堆，从最后一个非叶子结点 (n-2)/2 开始调整元素，直到第一个元素调整结束，此时大顶堆构造完成；
2. 开始堆排序过程，参见上面的 [堆排序基本思想]

• 注意：printVector需自己实现

#include <iostream>
#include <vector>
#include <algorithm>
#include "print.h"

using namespace std;

/**
 * 调整堆的过程，从第i个结点开始调整堆
 * @param nums
 * @param i
 * @param n
 */
void adjustHeap(vector<int>& nums, int i, int n){
    if(i >= n)
        return;

    int maxIdx = i;
    int left = 2*i+1, right = 2*i+2;

    if(left < n && nums[left] > nums[maxIdx])
        maxIdx = left;
    if(right < n && nums[right] > nums[maxIdx])
        maxIdx = right;

    if(maxIdx != i){
        swap(nums[maxIdx], nums[i]);
        adjustHeap(nums, maxIdx, n);
    }
}

/**
 * 生成大顶堆，从最后一个非叶子结点开始调整
 * @param nums
 */
void makeHeap(vector<int>& nums){
    int n = nums.size();
    for(int i = (n-2)/2; i >= 0; i--){
        adjustHeap(nums, i, n);
    }
}

/**
 * 堆排序
 * @param nums
 * @return
 */
void heapSort(vector<int>& nums){
    int n = nums.size();
    for(int i = n-1; i >= 0; i--){
        swap(nums[i], nums[0]);
        adjustHeap(nums, 0, i); // 长度在缩小
    }
}


int main(){
    vector<int> nums = {1,6,5,3,2,8,9};

    // 构造大顶堆
    printVector(nums);
    makeHeap(nums);
    printVector(nums);

    // 堆排序
    heapSort(nums);
    printVector(nums);

    return 0;
}

参考资料

• 图解排序算法(三)之堆排序 https://www.cnblogs.com/chengxiao/p/6129630.html
• 堆排序动画演示及代码实现：https://www.youtube.com/watch?v=j-DqQcNPGbE