云一网站建设,华夏名网vps免费网站管理助手,怀化高速网站,软件系统开发的大概步骤本文以大根堆为例#xff0c;用数组实现#xff0c;它的nums[0]是数组最大值。
时间复杂度分析#xff1a;
建堆o(n)
插入删除o(logn)
堆排序O(nlogn)
首先上代码
#includebits/stdc.husing namespace std;
void down(vectorintnums, int idx, i…本文以大根堆为例用数组实现它的nums[0]是数组最大值。
时间复杂度分析
建堆o(n)
插入删除o(logn)
堆排序O(nlogn)
首先上代码
#includebits/stdc.husing namespace std;
void down(vectorintnums, 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 nnums[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(vectorintnums, 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(vectorintnums)
{int n nums.size();for (int i n - 1; i 0; --i){if (2 * i 1 n - 1)down(nums, i,n);}}void heapinsert(vectorintnums,int val)
{nums.emplace_back(val);int n nums.size();up(nums, n - 1);
}void heapdel(vectorintnums)
{int n nums.size();nums[0] nums[n - 1];nums.pop_back();--n;down(nums, 0, n - 1);
}
void heapsort(vectorintnums)
{int n nums.size();while (n 1){swap(nums[0], nums[n - 1]);down(nums, 0, n-1);--n;}
}int main()
{vectorintnums { 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)
