03 堆排序

堆排序简介

算法思想：

​ 堆排序是对简单选择排序的改进，其核心思想是利用大根堆或者小根堆的树形结构，不断获取堆顶元素存入排序序列。大根堆是指一棵二叉树的每个节点值都大于或者等于它的左右子节点值，其根节点为最大值；小根堆反之。

​ 实现堆排序由两个关键任务：一是要构建大根堆或者小根堆；二是在取出堆顶之后，调整堆保持大根堆或者小根堆的树形结构。

​ 堆构建过程：堆构建有自上而下和自下而上两种方法，我们采用简单的自上而下构建

• 根据数组顺序插入树节点
• 如果插入节点值小于父节点，继续插入其他节点
• 如果插入节点值大于父节点，那么需要将该节点不断上浮，直到找到合适的插入位置
• 需要注意的是大根堆或者小根堆都是一棵完全二叉树，可以直接使用数组映射完全二叉树，不需要去另外构建树节点结构体；使用数组映射完全二叉树，索引从 0 开始具有如下性质：
  • 当前节点的父节点索引为(i-1)/2
  • 当前节点的左节点索引为2*i+1
  • 当前节点的左节点索引为2*i+2 = 2*(i+1)

​ 堆调整过程：

• 取出堆顶之后，用最后一个叶子节点与堆顶交换
• 因为最后一个叶子节点是数组的最小元素，所以将它放到大根堆堆顶，就破坏大根堆堆的树形结构，需要调整堆
• 选取根节点的左右节点中较大的节点与当前根节点交换
• 交换后如果破坏了子树的堆结构，就需要按照上述调整步骤递归地调整堆结构

执行样例：

输入：[29,10,14,37,16,25,20]

为了友好展示快排的效果我们稍微调整了一下之前的例子，删去了重复的元素

1. 大根堆构建过程

2. 堆排序过程

算法实现：

// 下沉调整大根堆，比较节点及其子节点，节点值大的子节点与父节点交换
void sink(vector<int> &nums, int i,int heapSize){
    if(heapSize==0 || nums.empty()) return;

    // 找到当前节点、左节点、右节点中较大的一个节点索引
    int bigger = i;
    int leftChild = 2*i+1;
    if(leftChild < heapSize){
        bigger = nums[leftChild] > nums[i] ? leftChild:i;
    }
    int rightChild = 2*i+2;
    if(rightChild < heapSize){
        bigger = nums[rightChild] > nums[bigger] ? rightChild:bigger;
    }

    // 如果较大节点是左右节点中的一个，交换当前节点和较大节点
    if(bigger!=i){
        swap(nums[i],nums[bigger]);
        sink(nums,bigger,heapSize); // 递归调整
    }
}

void buildHeap(vector<int> &nums, int heapSize){
    // 从最后一个非叶子节点开始构造
    int i=(heapSize-1)/2;
    for(i;i>=0;--i){
        sink(nums,i,heapSize);
    }
}

// 递归排序时，堆根节点先与最后一个节点进行交换，交换后，堆大小减1，并对根节点进行下沉调整
void sort(vector<int> &nums, int &heapSize){
	swap(nums[0], nums[heapSize - 1]);
	--heapSize;
	sink(nums,0,heapSize);
}

void heapSort(vector<int> &nums){
    int heapSize = nums.size();
    buildHeap(nums,heapSize);
    for(int i=0;i<nums.size()-1;++i){
        sort(nums,heapSize);
    }
}

912 排序数组 (opens new window)

给你一个整数数组 nums，请你将该数组升序排列。

示例：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

解析：

class Solution {
public:
    void sink(vector<int>& nums, int root, int heapSize){
        if(heapSize <=0 || nums.empty()){
            return;
        }
        int bigger = root;
        int leftChild = 2*root+1;
        int rightChild = 2*root+2;
        if(leftChild<heapSize){
            bigger = nums[leftChild] > nums[root]?leftChild:root;
        }
        if(rightChild<heapSize){
            bigger = nums[rightChild] > nums[bigger]?rightChild:bigger;
        }

        if(bigger!=root){
            swap(nums[root],nums[bigger]);
            sink(nums,bigger,heapSize);
        }
    }

    void bulidHeap(vector<int>& nums, int heapSize){
        for(int root = (heapSize-1)/2;root>=0;--root){
            sink(nums,root,heapSize);
        }
    }

    void top(vector<int>& nums, int& heapSize){
        swap(nums[0],nums[heapSize-1]);
        --heapSize;
        sink(nums,0,heapSize);
    }

    vector<int> sortArray(vector<int>& nums) {
        int heapSize = nums.size();
        bulidHeap(nums,heapSize);
        for(int i=0;i<nums.size();++i){
            top(nums,heapSize);
        }
        return nums;
    }
};