排序-堆排序

一、堆排序

1.1、堆的基本概念

1. 堆结构是用数组实现的完全二叉树
2. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆—升序
3. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆—降序
4. 优先级队列的实现就是堆结构

1.2、完全二叉树的数组表示

1. 每层都是满的或者每层都是从左到右填充的
2. 以数组来进行存储，从0开始存储，那么对于任意一个节点i，左孩子为2i+1，右孩子为2i+2；如果从1开始存储，那么对于任意一个节点i，左孩子为2i，右孩子为2i+1

1.3、核心操作

• 向上调整，建堆

// 某个数处在index位置，往上继续移动voidheapInsert(vector<int>&arr,intindex){// 往上移动，直到找到合适的位置或者到达顶部----两个条件while(arr[index]>arr[(index-1)/2]){swap(arr[index],arr[(index-1)/2]);index=(index-1)/2;// 往上移动}}

• 向下调整，调整堆

// 节点index上的值变小，需要向下移动// heapSize: 堆的大小（有效范围）voidheapify(vector<int>&arr,intindex,intheapSize){intleft=index*2+1;// 左孩子索引// 当还有左孩子时（没有左孩子就一定没有右孩子）while(left<heapSize){// 找出左右孩子中较大的那个intlargest=left+1<heapSize&&arr[left+1]>arr[left]?left+1// 右孩子存在且更大:left;// 左孩子更大或没有右孩子// 父节点和较大的孩子比较largest=arr[largest]>arr[index]?largest:index;if(largest==index){break;// 父节点已经是最大，不需要调整}// 交换父节点和较大的孩子swap(arr[largest],arr[index]);// 继续向下调整index=largest;left=index*2+1;}}

• 交换函数

void swap(vector<int>& arr, int a, int b) { using std::swap; swap(arr[a], arr[b]); }

1.4、堆排序

voidheapSort(vector<int>&arr){intn=arr.size();// 数组长度if(n==0||n<2)return;// 数组为空或者只有一个元素，不需要排序for(inti=0;i<n;++i)// O(n)heapInsert(arr,i);// 建堆 O(logn)swap(arr,0,--n);// 把堆顶和最后一个元素交换，让最大的元素来到最后while(n>0){// 还有元素需要排序 O(n)heapify(arr,0,n);// 把剩下的元素重新堆化 O(logn)swap(arr,0,--n);// 把堆顶和最后一个元素交换，让最大的元素来到最后 O(1)}}

最终时间复杂度为O(nlogn)，空间复杂度为O(1)。

建立堆过程还可以再次优化，只需要从最后一个非叶子节点开始往上建堆即可;因为最后一个非叶子节点以下的元素已经是堆结构了。

for(inti=n/2-1;i>=0;--i)// 从最后一个非叶子节点开始往上建堆heapify(arr,i,n);

1.5、堆排序过程

以数组[4，10，3，5，1]构建大根堆

• 构建堆后:[10, 5, 3, 4, 1]
• 排序过程：
  交换堆顶元素和最后一个元素，然后重新调整堆结构
  
  交换 10 和 1: [1, 5, 3, 4, 10]
  
  调整堆: [5, 4, 3, 1, 10]
  

交换 5 和 1: [1, 4, 3, 5, 10]

调整堆: [4, 1, 3, 5, 10]

交换 4 和 3: [3, 1, 4, 5, 10]

调整堆: [3, 1, 4, 5, 10]

交换 3 和 1: [1, 3, 4, 5, 10]

最终结果: [1, 3, 4, 5, 10]

1.6、C++中STL中的堆操作

#include<queue>#include<vector>#include<algorithm>#include<functional>voidstlHeapOperations(){// 1. 容器适配器 - priority_queuepriority_queue<int>maxHeap;// 默认大根堆priority_queue<int,vector<int>,greater<int>>minHeap;// 小根堆// 2. 算法函数（在 <algorithm> 中）vector<int>arr={3,1,4,1,5,9};// 构建最大堆make_heap(arr.begin(),arr.end());// 堆操作后: [9, 5, 4, 1, 1, 3]// 向堆中添加元素arr.push_back(6);push_heap(arr.begin(),arr.end());// 从堆中移除最大元素pop_heap(arr.begin(),arr.end());arr.pop_back();// 堆排序sort_heap(arr.begin(),arr.end());// 排序后: [1, 1, 3, 4, 5, 9]// 检查是否为堆boolisHeap=is_heap(arr.begin(),arr.end());}

1.7、扩展题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说比较小。请问这个几乎有序的数组的最快排序方法是？

堆排序可以解决这个问题，因为堆排序的时间复杂度是O(nlogk)，远远小于O(n^2)。

原因：
假设k=6，那么堆的大小就是7，先从前7个元素建立小根堆/大根堆；然后依次把后面的元素插入到堆中，每次插入之后再重新调整堆结构，每次调整会将堆顶元素弹出，然后再把后面的元素插入到堆中。

时间复杂度为O(nlogk)，空间复杂度为O(k)。

#include<iostream>#include<queue>#include<vector>#include<functional>voidsortedArrDistanceLessK(vector<int>&arr,intk){priority_queue<int,std::vector<int>,std::greater<int>>minHeap;// 小根堆intindex=0;for(;index<=std::min((int)arr.size(),k);++index){// 先将前k个元素放入小根堆中minHeap.push(arr[index]);}inti=0;for(;i<arr.size();++i,index++){// 遍历数组minHeap.push(arr[index]);// 把当前元素放入小根堆中arr[i]=minHeap.top();// 把堆顶元素放到当前位置minHeap.pop();// 弹出堆顶元素}while(!minHeap.empty()){arr[i++]=minHeap.top();// 把堆顶元素放到当前位置minHeap.pop();// 弹出堆顶元素}}

1.8、为什么要手写堆结构

系统提供的堆的局限性：

1. 无法修改中间元素：priority_queue不支持修改堆中任意元素

2. 无法指定比较器：有时需要自定义复杂的比较逻辑

3. 无法批量建堆：系统堆通常是逐个插入

4. 无法控制内存：某些嵌入式环境需要手动管理内存

二、实操演练

2.1、Leetcode 506 相对名次

题目描述:给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：

• 名次第 1 的运动员获金牌 “Gold Medal” 。
• 名次第 2 的运动员获银牌 “Silver Medal” 。
• 名次第 3 的运动员获铜牌 “Bronze Medal” 。
• 从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 “x”）。

使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

示例 1：

输入：score = [5,4,3,2,1]

输出：[“Gold Medal”,“Silver Medal”,“Bronze Medal”,“4”,“5”]

解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2：

输入：score = [10,3,8,9,4]

输出：[“Gold Medal”,“5”,“Bronze Medal”,“Silver Medal”,“4”]

解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。

解题思路：

1. 使用大根堆来存储得分和索引
2. 从堆中逐个弹出元素，根据弹出的顺序确定名次
3. 将名次信息存入结果数组

classSolution{public:vector<string>findRelativeRanks(vector<int>&score){// 使用堆排序，建立最大堆intlength=score.size();vector<string>ret(length);// 得分，索引priority_queue<pair<int,int>>maxHeap;for(inti=0;i<length;++i){maxHeap.push({score[i],i});}intrank=1;while(!maxHeap.empty()){auto[scoreVal,index]=maxHeap.top();maxHeap.pop();if(rank==1){ret[index]="Gold Medal";}elseif(rank==2){ret[index]="Silver Medal";}elseif(rank==3){ret[index]="Bronze Medal";}else{ret[index]=to_string(rank);}rank++;}returnret;}};

2.2、LeetCode 703 数据流中的第K大元素

题目描述：设计一个找到数据流中第 k 大元素的类（class）。

注意是排序后的第 k 个最大元素，不是第 k 个不同的元素。

实现 KthLargest 类：

• KthLargest(int k, int[] nums) 初始化对象，其中 nums 是传递给构造函数的整数数组，k 表示每次查找的第 k 大元素。
• int add(int val) 将 val 插入数据流 nums 后得到的新数据流中，并返回当前数据流中第 k 大的元素。
  示例：
  
  输入：[“KthLargest”,“add”,“add”,“add”,“add”,“add”], [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
  
  输出：[null,4,5,5,8,8]
  
  解释：
  
  KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
  
  kthLargest.add(3); // 返回 4
  
  kthLargest.add(5); // 返回 5
  
  kthLargest.add(10); // 返回 5
  
  kthLargest.add(9); // 返回 8
  
  kthLargest.add(4); // 返回 8
  

解题思路：

1. 使用最小堆，维护大小为k的元素集合
2. 最小堆的堆顶就是第k大的元素

classKthLargest{public:KthLargest(intk,vector<int>&nums){this->m_count=k;// 先加入所有元素，建立小根堆for(constauto&val:nums){minHeap.push(val);}// 堆大小超过k，弹出多余元素while(minHeap.size()>k){minHeap.pop();}}intadd(intval){minHeap.push(val);if(minHeap.size()>m_count){minHeap.pop();}returnminHeap.top();}private:intm_count;priority_queue<int,vector<int>,greater<int>>minHeap;};