堆排序学习笔记

在学习堆排序之前，我们先来了解一下堆这种数据结构。

堆的概念

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

堆必须是一个 完全二叉树 。
堆序性：堆中任意节点的值总是不大于或不小于其子节点的值。

根据堆序性，我们可以将堆分为两种类型：

大顶堆：每个节点的值都大于或等于其子节点的值
小顶堆：每个节点的值都小于或等于其子节点的值

所以，如果一个完全二叉树的一个节点即大于其父节点，又大于其子节点，那么这个树就不是一个堆。小于同理。

Note

完全二叉树的性质

完全二叉树只允许最后一层的节点可以不是满的
最后一行的节点必须从左到右依次排列，不能有间隔

完全二叉树

堆的存储

堆通常使用数组来存储，数组中的元素按照 层序遍历 的顺序存储，根节点存储在数组的第一个位置，即 a[0] 。

对于任意一个节点 a[i] ，它的左子节点存储在 a[2*i+1] ，右子节点存储在 a[2*i+2] 。

堆的存储

堆的基本操作

堆的基本操作有下沉和上浮两种。

下沉：将一个节点向下移动，直到满足堆序性。具体操作是将当前节点与其最大（或最小）子节点交换。
上浮：将一个节点向上移动，直到满足堆序性。具体操作是比较当前节点与其父节点的大小，若不满足堆序性则交换。

下沉操作

假设我们试图构建一个大顶堆，对于如下图中的一个堆，可以发现只有根节点破坏了大顶堆的堆序性。

我们需要将此节点（破坏了堆序性的节点）进行下沉操作。对于大顶堆的下沉操作，是将此节点与其最大子节点进行比较，若小于其最大子节点则进行交换，持续比较、交换，直到此节点大于其子节点或移动到底部为止。

上浮操作

假设我们同样试图构建一个大顶堆，对于如下图中的一个堆，可以发现只有最后一个元素破坏了堆序性。

我们需要将此节点与其父节点比较，若大于父节点则交换，直到无法上移为止。

建堆

建堆是指将一个无序数组转换为一个堆。有两种方法可以实现建堆，分别是 自顶向下 和 自底向上 。

自顶向下：对应的操作是上浮，将元素一个一个插入到堆的最后一个位置，然后进行上浮操作。
自底向上：对应的操作是下沉，先将数组中的元素按照 层序遍历 的顺序存储到一个完全二叉树，然后从最后一个非叶子节点开始，依次进行下沉操作。

自顶向下建堆

时间复杂度为 O(NlogN) 。

开始遍历，对于每个元素分为两步操作：

将新元素插入堆的最后一个位置
对新元素进行上浮操作

如下图所示，先将元素 3 插入根节点位置，然后插入元素 4 到堆的最后一个位置，然后对元素 4 进行上浮操作。

自顶向下

元素 4 的上浮操作结束后，接着插入元素 5 到堆的最后一个位置，然后对元素 5 进行上浮操作。

自顶向下

自底向上建堆

时间复杂度为 O(N) ，优于自顶向下建堆法。

先将数组中的元素按照 层序遍历 的顺序存储到一个完全二叉树中，然后开始遍历，对于每一个元素只有一步操作：

选取最后一个非叶子节点（最后一个父节点），进行下沉操作。

如下图所示，先数组中的元素按照层序遍历的顺序存储到一个完全二叉树。

自底向上

选取最后一个非叶子节点，即节点 5，开始下沉操作。

自底向上

接着选取另一个非叶子节点，即节点 4，开始下沉操作。

自底向上

优先队列

优先队列是一种特殊的队列，它的出队顺序是按照元素的优先级来决定的。我们可以使用堆来实现优先队列。大顶堆可以实现最大优先级队列，小顶堆可以实现最小优先级队列。

这里以最小优先级队列为例，需要使用堆的下沉操作来实现出队操作，使用堆的上浮操作来实现入队操作。

出队操作

出队操作即弹出堆顶元素，弹出后需要将堆的最后一个元素放到堆顶，然后进行下沉操作。

入队操作

入队操作即将元素插入到堆的最后一个位置，然后进行上浮操作。

堆排序

堆排序是一种原地排序算法，它的基本思想是将数组构建成一个大顶堆/小顶堆，然后将堆顶元素与堆的最后一个元素交换，然后对剩余的元素进行下沉操作，直到整个数组有序。

堆排序

算法实现

#include <iostream>
#include <vector>

using namespace std;

// 递归方式构建大顶堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(vector<int> &arr, int len, int index) {
    int left = 2 * index + 1;  // index的左子节点
    int right = 2 * index + 2; // index的右子节点

    int max_idx = index; // 用于记录最大值的下标
    if (left < len && arr[left] > arr[max_idx]) {
        max_idx = left;
    }
    if (right < len && arr[right] > arr[max_idx]) {
        max_idx = right;
    }

    if (max_idx != index) {
        swap(arr[max_idx], arr[index]);
        adjust(arr, len, max_idx);
    }
}

// 堆排序
void heap_sort(vector<int> &arr, int size) {
    // 构建大顶堆（从最后一个非叶子节点向上）
    for (int i = size / 2 - 1; i >= 0; i--) {
        adjust(arr, size, i);
    }

    // 调整大顶堆
    for (int i = size - 1; i >= 1; i--) {
        swap(arr[0], arr[i]); // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);    // 将未完成排序的部分继续进行堆排序
    }
}

// 构建小顶堆
void adjust_min(vector<int> &arr, int len, int index) {
    int l = 2 * index + 1;
    int r = 2 * index + 2;

    int max_idx = index;
    if (l < len && arr[l] < arr[max_idx]) {
        max_idx = l;
    }
    if (r < len && arr[r] < arr[max_idx]) {
        max_idx = r;
    }

    if (max_idx != index) {
        swap(arr[index], arr[max_idx]);
        adjust_min(arr, len, max_idx);
    }
}

void heap_sort_min(vector<int> &arr, int size) {
    // 构建小顶堆，从第一个非叶子节点开始下沉
    for (int i = size / 2 - 1; i >= 0; --i) {
        adjust_min(arr, size, i);
    }

    // 开始排序，交换根节点和最后一个节点，然后对根节点进行下沉
    for (int i = size - 1; i >= 1; --i) {
        swap(arr[0], arr[i]);
        adjust_min(arr, i, 0);
    }
}

int main() {
    vector<int> arr = {8, 1, 14, 3, 21, 5, 7, 10};
    heap_sort(arr, arr.size());

    for(int i : arr) {
        cout<<i<< " ";
    }

    cout<< "\n";
    arr = {8, 1, 14, 3, 21, 5, 7, 10};
    heap_sort_min(arr, arr.size());

    for(int i : arr) {
        cout<<i<< " ";
    }
    return 0;
}

堆排序与其他排序算法的比较

堆排序、快速排序和归并排序，他们的时间复杂度都为 O(NlogN)，但堆排序是一个原地排序算法，所以其空间复杂度最小，为 O(1)，快速排序和归并排序的空间复杂度分别为 O(logN) 和 O(N)。

参考

【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆（视频）