leetcode每日一题
[1738] 找出第 K 大的异或坐标值
[1744] 你能在你最喜欢的那天吃到你最喜欢的糖果吗?
[231] 2的幂
堆排复习
[461] 汉明距离
[1190] 反转每对括号间的子串
[1707] 与数组中元素的最大异或值
[810] 黑板异或游戏
[1035] 不相交的线
[692] 前K个高频单词
[872] 叶子相似的树
[1442] 形成两个异或相等数组的三元组数目
[993] 二叉树的堂兄弟节点
[421] 数组中两个数的最大异或值
[13] 罗马数字转整数
[12] 整数转罗马数字
[1269]. 停在原地的方案数
[1310] 子数组异或查询
[1734] 解码异或后的排列
本文档使用 MrDoc 发布
-
+
首页
堆排复习
堆排实现:先实现大堆序,即根节点大于两个子节点,从最后一个非叶子节点开始检查(也可以直接从最后一个节点开始检查,浪费时间而已),判断该节点是否比两个子节点小,若小,与最大的子节点交换,这里交换完毕后需要递归更新交换后的节点是否依旧符合大堆序,依次遍历到根节点,则大堆序成立。然后将最大值交换到最末尾位置,递归更新根节点保证大堆序成立,直到所有数据排序完成。 ```cpp class Solution { public: void UpdateNode(vector<int> &nums,int nums_index,int end_index) { int left_index = 2 * nums_index + 1; int right_index = 2 * nums_index + 2; if(left_index >= end_index) return; //没有左右子树(因为是满二叉树,没有左子树就不存在右子树) int change_index = left_index; if(right_index < end_index && nums[right_index] > nums[left_index]) { change_index = right_index; //找到左右子树中最大的值 } if(nums[nums_index] < nums[change_index]) //存在子节点值大于根节点值 { std::swap(nums[nums_index],nums[change_index]); UpdateNode(nums,change_index,end_index); //递归修正子节点 保持堆排格式 } } //创建堆 格式为 根节点的值一定比左右子树的值大 void createDeap(vector<int> &nums,int end_index) { //从第一个非叶子节点开始向上遍历 int start_index = end_index / 2 - 1; for (int i = start_index; i >= 0; -- i) { UpdateNode(nums,i,end_index); } } vector<int> sortArray(vector<int>& nums) { if(nums.empty()) return nums; createDeap(nums,(int)nums.size()); //创建堆 for(int i = (int)nums.size() - 1; i > 0; --i) //依次交换最大值到末尾 { std::swap(nums[0],nums[i]); UpdateNode(nums,0,i); //更新交换后的根节点 保证大堆序 } return nums; } }; ```
ty
2021年5月27日 11:42
转发文档
收藏文档
上一篇
下一篇
手机扫码
复制链接
手机扫一扫转发分享
复制链接
阅读量
次
本站总访问量
次
本站访客数
人次
Markdown文件
分享
链接
类型
密码
更新密码