大顶堆和小顶堆
1.一颗二叉树, 里面所有的根节点都比孩子节点要大, 就是大顶堆; 小顶堆同理
2.怎么构建一个大顶堆, 只需要挨个把非叶子节点调整成满足大顶堆的要求, 也就是和两个孩子节点去比较, 然后和最大的交换; 如果发生了交换, 那么还需要递归地处理孩子的大顶性质
堆排序
1.已经将长度为n的原始数组构建成了一个大顶堆, 怎么用于排序?
2.每次将顶元素和数组最后一个元素交换, 所以最大的元素已经排好位置
3.交换之后剩下的 n-1 个元素的结构又不满足大顶堆了, 所以需要对这 n-1 个元素继续调整堆, 使得这n-1个元素还满足大顶堆的性质
4.继续将现在的顶交换到倒数第二个位置, 所以第二大的元素已经排好位置
5.交换之后剩下的 n-2 个元素的结构又不满足大顶堆了, 所以需要对这 n-2 个元素继续调整堆, 使得这n-2个元素还满足大顶堆的性质
6.如此交替进行 [根节点和最后一个元素交换] 和 [调整堆], 最终得到排序好的数组
class Solution {
public:
// 调整堆: 将当前元素和它的两个孩子节点进行交换, 把最大的放在当前的节点位置;
// 如果当前的位置在数组中是idx, 那么左孩子是 2 * idx + 1, 右孩子 2 * idx + 2
// 如果发生了交换, 那么还需要递归地调整发生交换的节点, 使得满足最大堆的性质
void maxHeapify(vector<int>& nums, int len, int idx) {
int lSon = 2 * idx + 1;
int rSon = 2 * idx + 2;
int maxIdx = idx;
if (lSon < len && nums[lSon] > nums[maxIdx]) maxIdx = lSon;
if (rSon < len && nums[rSon] > nums[maxIdx]) maxIdx = rSon;
// 如果maxIdx的值有更新
if (maxIdx != idx) {
swap(nums[maxIdx], nums[idx]); // 将大元素调整到顶部
maxHeapify(nums, len, maxIdx); // 递归调整其他不满足大顶堆性质的部分
}
}
// 构建堆: 从最后一个非叶子节点依次调整堆, 直到满足大顶堆的性质
// 从最后一个非叶子节点开始进行大顶堆构建, 顺序从右到左, 从上到下
// 最后一个非叶子节点的index = size / 2 - 1;
void heapSort(vector<int>& nums, int size) {
for (int i = size / 2 - 1; i >= 0; --i) {
maxHeapify(nums, size, i);
}
// 开始从最后一个节点开始置换, 将堆顶元素置换到数组末尾
// 只剩最后1个节点就不用换了, 倒数第二次已经换完
for (int i = size - 1; i >= 1; --i) {
swap(nums[0], nums[i]);
// 完成堆顶元素的置换, 然后继续调整堆
maxHeapify(nums, i, 0);
}
}
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
heapSort(nums, n);
return nums;
}
};
转载请注明来源, from goldandrabbit.github.io
