C++数据结构之堆详解

C++数据结构之堆详解

什么是堆

堆是一种完全二叉树。

堆分为大根堆和小根堆，大根堆满足每个节点的值都大于等于它的子节点，小根堆满足每个节点的值都小于等于它的子节点。

堆的实现

常见的实现堆的方式有数组和链表两种。

数组

由于二叉堆是完全二叉树，所以可以用数组来实现：

对于一个节点i，它的左子节点的下标是2 * i + 1，右子节点的下标是2 * i + 2，它的父节点的下标是(i - 1) / 2。

例如：

           1
         /  \
        2    3
       / \  / \
      4  5 6   7 

用数组实现时，可以按层级顺序将节点存储在数组中，下标为i的节点的左子节点为2 * i + 1，右子节点为2 * i + 2，其父节点为(i - 1) / 2。

上述二叉树可以用数组实现如下：

[1, 2, 3, 4, 5, 6, 7]

数组的第一个元素永远是根节点。

链表

堆也可以用链表来实现，每个节点包含指向左右子节点的指针和节点的值。

堆的基本操作

插入元素

要在堆中插入元素，必须保持堆的连通性，以及满足堆的特性。在插入一个新节点时，先插入到堆的最后一个位置，然后从该节点开始向上比较，如果该节点的值大于它的父节点的值，就交换它们的位置。

例如，现在有以下的大根堆：

          4
        /   \
       3     2
      / \   /
     1   5 6

要在这个堆中插入一个元素7，首先将它插入到堆的最后一个位置：

          4
        /   \
       3     2
      / \   / \
     1   5 6   7

然后从7节点开始向上比较，发现它大于2，所以将它与2交换位置：

          4
        /   \
       3     7
      / \   / \
     1   5 6   2

再与6交换位置：

          4
        /   \
       3     7
      / \   / \
     1   5 6   2

最终变成以下堆：

          7
        /   \
       3     6
      / \   / \
     1   5 4   2

删除元素

要在堆中删除一个元素，只能删除堆的根节点。将根节点移除后，将堆的最后一个元素放到根节点的位置，然后从该节点开始向下比较，如果该节点的值小于它的子节点的值，就交换它们的位置。

例如，现在有以下的大根堆：

          7
        /   \
       3     6
      / \   / \
     1   5 4   2

要从这个堆中删除最大的元素7，首先将它移除，并将堆的最后一个元素2放到根节点的位置：

          2
        /   \
       3     6
      / \   / 
     1   5 4   

然后从2节点开始向下比较，发现它小于6，所以将它与6交换位置：

          6
        /   \
       3     2
      / \   / 
     1   5 4   

再交换3和6的位置：

          6
        /   \
       1     2
      / \   / 
     3   5 4   

最终变成以下堆：

          6
        /   \
       1     4
      / \   / 
     3   5 2   

堆排序

堆排序使用堆的特性来排序元素。首先将所有元素插入到堆中，然后从堆中依次取出根节点，就可以得到一个有序序列。

例如，要对以下数组排序：

[3, 2, 5, 1, 4]

首先将它们插入到堆中：

          5
        /   \
       3     4
      / \   / 
     1   2   

然后依次从堆中取出根节点，就可以得到一个有序序列：

1, 2, 3, 4, 5

示例说明

示例1

以下是一个从小到大的堆排序示例：

#include <iostream>
#include <vector>

// 堆排序
void heap_sort(std::vector<int>& nums)
{
    // 构建初始堆
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(nums, n, i);

    // 依次取出堆顶元素
    for (int i = n - 1; i >= 0; i--)
    {
        std::swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

// 堆排序的调整函数
void heapify(std::vector<int>& nums, int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && nums[left] > nums[largest])
        largest = left;

    if (right < n && nums[right] > nums[largest])
        largest = right;

    if (largest != i)
    {
        std::swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

int main()
{
    std::vector<int> nums{ 3, 2, 5, 1, 4 };

    heap_sort(nums);

    for (auto num : nums)
        std::cout << num << " ";

    return 0;
}

输出结果：

1 2 3 4 5

示例2

以下是一个从大到小的堆排序示例：

#include <iostream>
#include <vector>

// 堆排序
void heap_sort(std::vector<int>& nums)
{
    // 构建初始堆
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(nums, n, i);

    // 依次取出堆顶元素
    for (int i = n - 1; i >= 0; i--)
    {
        std::swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

// 堆排序的调整函数
void heapify(std::vector<int>& nums, int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && nums[left] < nums[largest])
        largest = left;

    if (right < n && nums[right] < nums[largest])
        largest = right;

    if (largest != i)
    {
        std::swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

int main()
{
    std::vector<int> nums{ 3, 2, 5, 1, 4 };

    heap_sort(nums);

    for (auto num : nums)
        std::cout << num << " ";

    return 0;
}

输出结果：

5 4 3 2 1