C++最大堆的实现,使用Buildheap/Siftdown算法
时间: 2024-10-17 10:08:04 浏览: 0
在C++中,可以使用数组来实现大顶堆,这是一种特殊的完全二叉树结构,满足堆性质:即每个节点都大于或等于其子节点。实现大顶堆有两步基本操作:建堆和调整堆。
**建堆(Heapify or BuildHeap)**:
- 初始化堆:将未排序的元素依次插入到堆中,并从最后一个非叶子节点开始向上调整,保证每一步都是满足堆性质的。
- 使用`build_heap()`函数,从最后一个非叶子节点(即最后一个元素的父节点索引减一)开始,向下遍历,每次都将当前节点与它的孩子中较大的交换,直到堆化完成。
```cpp
void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
```
**Siftdown算法(Sort Down)**:
- 当向堆中添加新元素后,如果这个元素违反了堆的特性(即父节点小于子节点),则需要将其与父节点交换,然后继续与其上一个父节点比较,直到满足堆性质为止。这种过程被称为“下沉”(sifting down)。
```cpp
void siftDown(int arr[], int n, int i) {
while (i < n / 2) {
int largest = i;
int left = 2 * i + 1;
// 更新最大值位置
if (left < n && arr[left] > arr[largest])
largest = left;
// 再次检查右侧是否更大
if (2 * i + 2 < n && arr[2 * i + 2] > arr[largest])
largest = 2 * i + 2;
// 如果父节点不是最大,就交换它们并继续下沉
if (largest != i) {
swap(arr[i], arr[largest]);
i = largest; // 保持在新的最大节点处向下搜索
} else
break;
}
}
```
阅读全文