C++堆排序

图解排序算法(三)之堆排序

1.堆排序的概念

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

大顶堆：每个节点的值都大于其左右孩子节点的值。小顶堆：每个节点的值都小于其左右孩子节点的值。

2.堆排序基本思想与步骤

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤：

将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

3.代码实现

/* * @Description: 堆排序 * @Author: szq * @Github: https://github.com/MrQqqq * @Date: 2020-07-04 21:01:47 * @LastEditors: szq * @LastEditTime: 2020-07-04 22:14:52 * @FilePath: \cpp\src\heapsort.cpp */ #include<iostream> #include<queue> using namespace std; /** * @destription： 调整堆 * @param :nums：待调整的堆 i:调整的当前非叶子节点 length:数组长度 * @return: 没有返回值 */ void adjustHeap(vector<int> &nums,int i,int length){ int temp = nums[i];//取出当前元素 for(int k = i * 2 + 1;k < length;k = k * 2 + 1){//从i节点的左子节点开始，也就是2i+1出开始 if(k + 1 < length && nums[k] < nums[k+1]){//如果左子节点小于右子节点，k指向右子节点 k++; } //如果子节点大于父节点，将子节点的值赋给父节点(不用交换) if(nums[k] > temp){ nums[i] = nums[k]; i = k; } else{ break; } } nums[i] = temp;//将父节点的值放在最终的位置 } /** * @destription: 交换数组中i,j位置的值 * @param {type} nums:要交换的数组 i、j:位置 * @return: 没有返回值 */ void swap(vector<int> &nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } /** * @destription: 堆排序函数 * @param {type} nums:待排序数组 * @return: 没有返回值 */ void heapsort(vector<int> &nums){ int len = nums.size(); //构建大根堆 for(int i = len/2 - 1;i >= 0;i--){ adjustHeap(nums,i,len); } //交换对顶元素与末尾元素，并调整堆 for(int i = len - 1;i > 0;i--){ swap(nums,0,i); adjustHeap(nums,0,i); } } int main(){ vector<int> nums = {9,8,7,6,5,4,3,2,1}; heapsort(nums); for(int num : nums){ cout << num << " "; } cout << endl; }

4.STL中优先队列创建大（小）根堆

创建格式：

//升序队列，小顶堆 priority_queue <int,vector<int>,greater<int> > q; //降序队列，大顶堆，两种方式 priority_queue <int,vector<int>,less<int> >q; //priority_queue<int> q;//基本数据类型默认是大根堆 //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

示例：

/* * @Description: 使用priotity_queue实现大（小）根堆 * @Author: szq * @Github: https://github.com/MrQqqq * @Date: 2020-07-04 22:16:41 * @LastEditors: szq * @LastEditTime: 2020-07-04 22:32:38 * @FilePath: \cpp\src\priority_queue.cpp */ #include<vector> #include<queue> #include<iostream> using namespace std; int main(){ //创建大根堆的两种方式 //1.基本数据类型默认是大根堆 priority_queue<int> pq1; //2.标准格式 priority_queue<int,vector<int>,less<int>> pq2;//less是比较前一个元素和后一个元素的结果， //less小于的意思，因此整个队列是逆序的 //大根堆里添加元素 pq1.push(1); pq1.push(2); pq2.push(1); pq2.push(2); //测试大根堆顶部元素，大根堆顶部的元素为队列中最大的元素 cout << "大根堆pq1顶部元素为：" << pq1.top() << endl; cout << "大根堆pq2顶部元素为：" << pq2.top() << endl; //创建小根堆的方式 priority_queue<int,vector<int>,greater<int>> pq3;//greater是比较前一个元素和后一个元素的结果， //greater大于的意思，因此整个队列是顺序的 //向小根堆中添加元素 pq3.push(1); pq3.push(2); //测试小根堆顶部元素,小根堆顶部的元素为队列中最小的元素 cout <<"小根堆pq3顶部元素为：" << pq3.top() << endl; }

自定义数据类型创建大根堆：

/* * @Description: 用自定义数据创建大根堆小根堆 * @Author: szq * @Github: https://github.com/MrQqqq * @Date: 2020-07-04 22:44:54 * @LastEditors: szq * @LastEditTime: 2020-07-04 22:49:51 * @FilePath: \cpp\src\priority_queue_mydata.cpp */ #include <iostream> #include <queue> using namespace std; //方法1 struct tmp1 //运算符重载< { int x; tmp1(int a) {x = a;} bool operator<(const tmp1& a) const { return x < a.x; //大顶堆 } }; //方法2 struct tmp2 //重写仿函数 { bool operator() (tmp1 a, tmp1 b) { return a.x < b.x; //大顶堆 } }; int main() { tmp1 a(1); tmp1 b(2); tmp1 c(3); priority_queue<tmp1> d; d.push(b); d.push(c); d.push(a); while (!d.empty()) { cout << d.top().x << '\n'; d.pop(); } cout << endl; priority_queue<tmp1, vector<tmp1>, tmp2> f; f.push(b); f.push(c); f.push(a); while (!f.empty()) { cout << f.top().x << '\n'; f.pop(); } }