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
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C++数据结构之堆详解 - Python技术站
微信扫一扫 
支付宝扫一扫 