c++ 二叉堆 duildheap
时间: 2023-07-01 20:20:07 浏览: 59
二叉堆是一种经典的数据结构,可以用来实现优先队列等数据结构。二叉堆分为最大堆和最小堆两种形式,本文以最大堆为例介绍如何实现二叉堆的建堆操作 buildHeap()。
二叉堆可以用数组来表示,具体来说,如果一个节点的下标为 i,则它的左子节点的下标为 2i+1,右子节点的下标为 2i+2,父节点的下标为 (i-1)/2。
建堆操作 buildHeap() 的主要思路是从最后一个非叶子节点开始,依次向上调整节点,使得以该节点为根节点的子树成为一个合法的最大堆。具体实现时,可以从最后一个非叶子节点开始,依次向前遍历所有非叶子节点,对于每个节点,调用 siftDown() 函数将该节点及其子树调整为一个合法的最大堆。
下面是一个简单的 buildHeap() 函数的实现:
```c++
template <typename T>
void buildHeap(std::vector<T>& nums) {
// 从最后一个非叶子节点开始,依次向前遍历所有非叶子节点
for (int i = (nums.size() - 2) / 2; i >= 0; --i) {
siftDown(nums, i, nums.size());
}
}
template <typename T>
void siftDown(std::vector<T>& nums, int index, int size) {
int left = 2 * index + 1; // 左子节点下标
int right = 2 * index + 2; // 右子节点下标
int largest = index; // 记录最大值的下标
// 判断左子节点是否大于当前节点
if (left < size && nums[left] > nums[largest]) {
largest = left;
}
// 判断右子节点是否大于当前节点
if (right < size && nums[right] > nums[largest]) {
largest = right;
}
// 如果最大值下标不是当前节点下标,则交换两个节点的值,并递归调整以最大值下标为根节点的子树
if (largest != index) {
std::swap(nums[index], nums[largest]);
siftDown(nums, largest, size);
}
}
```
需要注意的是,在实现 buildHeap() 函数时,需要借助 siftDown() 函数来进行节点的调整。siftDown() 函数的实现思路是,首先找到当前节点的左子节点和右子节点,然后判断左子节点和右子节点中的最大值是否大于当前节点的值,如果是,则将最大值所在节点与当前节点交换,并递归调整以最大值所在节点为根节点的子树。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)