C++深入浅出讲解堆排序和堆

堆的定义

堆是一种特殊的树形数据结构，它满足以下两个特性：

• 堆是一个完全二叉树（Complete Binary Tree）；
• 堆中每个节点的值都大于等于（或小于等于）其左右子节点的值。

可以看出，堆一般分为两种类型：大根堆（Max Heap）和小根堆（Min Heap）。大根堆的每个节点的值都大于等于其左右子节点的值，小根堆则相反。

堆的应用

堆主要应用于优先队列、Top K 问题、求中位数等场景。

• 在优先队列中，堆可以快速地找到队列中的最大或最小值；
• 在 Top K 问题中，堆可以维护一个大小为 K 的堆，依次将数据插入堆中，最后堆中的数据即为前 K 大或前 K 小的元素；
• 求中位数问题可以通过维护两个堆来处理，使得左边堆的最大值小于右边堆的最小值。

堆的实现

堆可以通过数组来实现，因为完全二叉树可以被序列化成一个数组。

插入元素

插入元素时，可以将新元素插入到堆的最后一个位置，然后使用一个循环将新元素与其父节点进行比较，如果父节点的值小于新元素，则将父节点和新元素交换位置，直到新元素的父节点的值大于等于新元素的值为止。

删除元素

删除元素时，可以将堆中最后一个元素移到堆顶，然后让其与左右子节点中较大的值进行比较，如果较大的值大于该节点的值，则将其与较大的子节点交换位置，并继续向下比较。直到该节点的值大于等于其左右子节点的值为止。

堆排序

堆排序是一种不稳定的排序算法，它的时间复杂度为 O(nlogn)。

堆排序的思路

1. 构建大根堆（或小根堆）：将待排序数组构建成一个大根堆（或小根堆）；
2. 堆排序：将大根堆（或小根堆）根节点与最后一个叶子节点进行交换，并将交换后的最后一个叶子节点排除在堆的范围之外；此时，根节点可能不再满足堆的性质，因此需要将其与左右子节点中较大的节点进行比较并交换位置，然后继续向下比较，直到满足堆的性质为止；
3. 重复步骤 2，直到整个数组有序。

堆排序的实现

void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 从最后一个非叶子节点开始，依次向下调整堆
    for (int i = (n - 2) / 2; i >= 0; i--) {
        heapify(nums, i, n);
    }
    // 交换堆顶与最后一个叶子节点，并重新调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, 0, i);
    }
}

void heapify(vector<int>& nums, int i, int n) {
    int largest = i;
    int left = i * 2 + 1, right = i * 2 + 2;
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, largest, n);
    }
}

这里使用了一个辅助函数 heapify() 来调整堆，它将一个大小为 n 的数组 nums 中的第 i 个节点向下调整，使得以 i 为根节点的子树满足堆的性质。heapify() 的具体实现可以参考前面所述。

堆排序的示例

下面是一个堆排序的示例：

#include <iostream>
#include <vector>

using namespace std;

void heapify(vector<int>& nums, int i, int n);

void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 从最后一个非叶子节点开始，依次向下调整堆
    for (int i = (n - 2) / 2; i >= 0; i--) {
        heapify(nums, i, n);
    }
    // 交换堆顶与最后一个叶子节点，并重新调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, 0, i);
    }
}

void heapify(vector<int>& nums, int i, int n) {
    int largest = i;
    int left = i * 2 + 1, right = i * 2 + 2;
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, largest, n);
    }
}

int main() {
    vector<int> nums = {3, 8, 5, 2, 9, 7, 1, 4, 6};
    heapSort(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

输出结果如下：

1 2 3 4 5 6 7 8 9

这个例子演示了如何使用堆排序将无序数组 nums 排序。经过堆排序之后，数组 nums 变成了升序排列。