c++堆排序-建堆-插入-删除-排序

本文以大根堆为例，用数组实现，它的nums[0]是数组最大值。

时间复杂度分析：

建堆o(n)

插入删除o(logn)

堆排序O(nlogn)

首先上代码

#include<bits/stdc++.h>using namespace std;
void down(vector<int>&nums, int idx, int n)
{//删除时和由数组创建堆时用到int leftidx = 2 * idx + 1;int rightidx = 2 * idx + 2;if (leftidx >= n && rightidx >= n)return;if (rightidx >= n && nums[idx] >= nums[leftidx])return;if (rightidx < n&&nums[idx] >= nums[leftidx] && nums[idx] >= nums[rightidx])return;if (rightidx >= n || nums[leftidx] >= nums[rightidx]){swap(nums[idx], nums[leftidx]);down(nums, leftidx, n);}else{swap(nums[idx], nums[rightidx]);down(nums, rightidx, n);}
}void up(vector<int>&nums, int idx)
{//上滤操作由插入元素时用到，此处使用vector动态数组，不考虑静态数组插入元素过多导致过界拷贝扩容问题。int faridx = (idx - 1) / 2;if (idx == 0 || nums[idx] <= nums[faridx])return;swap(nums[idx], nums[faridx]);up(nums, faridx);
}void heapfy(vector<int>&nums)
{int n = nums.size();for (int i = n - 1; i >= 0; --i){if (2 * i + 1 <= n - 1)down(nums, i,n);}}void heapinsert(vector<int>&nums,int val)
{nums.emplace_back(val);int n = nums.size();up(nums, n - 1);
}void heapdel(vector<int>&nums)
{int n = nums.size();nums[0] = nums[n - 1];nums.pop_back();--n;down(nums, 0, n - 1);
}
void heapsort(vector<int>&nums)
{int n = nums.size();while (n> 1){swap(nums[0], nums[n - 1]);down(nums, 0, n-1);--n;}
}int main()
{vector<int>nums = { 2,1,4,6,5,8,0,7};heapfy(nums);for (auto& num : nums)cout << num <<" ";cout << "建队完成"<<endl;heapinsert(nums, 9);for (auto& num : nums)cout << num << " ";cout << "插入完成"<<endl;heapdel(nums);for (auto& num : nums)cout << num << " ";cout << "删除完成"<<endl;heapsort(nums);for (auto& num : nums)cout << num << " ";cout << "排序完成，堆结构已破坏" << endl;
}

读者可以复制代码到编译器里运行一下试试，帮助理解

它的主要思路参考力扣官方讲解

LeetCode 力扣官方分享 | 最大堆的基本内容和堆排序 - 知乎 (zhihu.com)