宿迁明远建设有限公司网站,男女做那些事免费网站,山东平台网站建设找哪家,网站未备案什么意思根据大顶堆的描述, 父节点的值始终大于子节点(如果有的话)的值, 再加上堆是完全二叉树, 可以用数组表示, 那么就可以用来进行排序.
具体做法就是, 对于随机排列的数组:
1. 首先将其构建成一个大顶堆, 根据堆的性质, 此时堆顶就是最大值.
2. 把堆顶元素与数组最后一个元素进行…根据大顶堆的描述, 父节点的值始终大于子节点(如果有的话)的值, 再加上堆是完全二叉树, 可以用数组表示, 那么就可以用来进行排序.
具体做法就是, 对于随机排列的数组:
1. 首先将其构建成一个大顶堆, 根据堆的性质, 此时堆顶就是最大值.
2. 把堆顶元素与数组最后一个元素进行交换, 也就是把最大值换至最后一个元素
3. 把元素个数减一, 重复上述两个步骤
可以看出最复杂的, 也就是构造大顶堆的过程, 对于一个随机排列的数组, 其构建大顶堆的步骤如下:
假设有一个数组A, 共有n(14)个元素(如图). 1. 首次构建时, 需要遍历所有的子树, 让所有的子树满足大顶堆性质, 而只有一个节点的子树则不需要遍历(因为不需要调整), 所以要从第一个非叶子节点的子树开始遍历, 构建大顶堆. 而第一个非叶子节点的子树根节点, 在数组中的下标为 n / 2 - 1(也就是6, 目前6不需要调整), 从此开始一直至0(注意当上层树发生变化时, 需要递归调整下层的树, 为什么要从下至上调整, 因为下层调整完成后, 已经把下层最大的调整至根节点了, 这样当根节点发生变化时, 只需要从上向下再调整一遍, 因为下层已经不可能有比上面更大的值了). 例子中的步骤为: 1. 首先遍历第一个非叶子节点, 14 / 2 - 1 6, 发现不用调整, 然后遍历5, 发现也不用调整, 然后遍历4, 交换4 9的值: 2. 遍历3, 交换3 8: 3. 遍历2, 不用动, 遍历1, 交换1 3, 然后发现68交换到3后, 3 7 8子树不需要动(就算需要动, 也不需要再动1 3 4了, 因为之前3 7 8已经调整过, 新上来的不可能取代已经上去的了): 4. 遍历0, 交换0 1, 交换1 3, : (3 7 8不再需要调整, 原因同上一步) 2. 首次构建完大顶堆后, 交换首个元素与最后一个元素的值, 然后重新构建大顶堆 1. 交换0 13: 2. 数组长度少一: 3. 从根节点开始重新构建大顶堆, 交换0 2, 交换2 5: 4. 这样又重新构建成了大顶堆, 重复上述步骤 代码:
leetcode链接(第912题): https://leetcode-cn.com/problems/sort-an-array/submissions/
(第215题)
void heapify(vectorint nums, int root, int max_index) {int left 2 * root 1;if (left max_index)return;int right 2 * root 2;int exchange_index left;if (right max_index nums[right] nums[left])exchange_index right;if (nums[root] nums[exchange_index]) {swap(nums[root], nums[exchange_index]);heapify(nums, exchange_index, max_index);}
}
vectorint sortArray(vectorint nums) {int total nums.size();for (int i total / 2 - 1; i 0; i --) {heapify(nums, i, total - 1);}int target_index total - 1;while (target_index 0) {swap(nums[0], nums[target_index]);target_index --;heapify(nums, 0, target_index);}return nums;
}
