最大堆排序的基本操作
时间: 2023-12-22 10:29:11 浏览: 66
最大堆排序的基本操作包括以下几个步骤:
1. 构建最大堆:将待排序的数组构造成一个最大堆。最大堆是一种满足父节点大于等于子节点的完全二叉树。构建最大堆的方法是从最后一个非叶子节点开始,依次向上调整每个节点,使其满足最大堆的性质。
2. 交换堆顶元素和最后一个元素:将最大堆的堆顶元素与最后一个元素交换位置,即将最大的元素放到数组的末尾。
3. 调整堆:将剩下的元素重新调整为最大堆。从堆顶开始,比较左右子节点的值,将较大的子节点与父节点交换位置,然后再对交换后的子节点进行调整,直到整个堆重新满足最大堆的性质。
4. 重复步骤2和步骤3,直到所有元素都被排序。
下面是一个用C++实现基于最大堆的堆排序的示例:
```cpp
#include <iostream>
using namespace std;
// 调整堆
void adjustHeap(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]);
// 递归调整交换后的子节点
adjustHeap(arr, n, largest);
}
}
// 堆排序
void heapSort(int arr[], int n) {
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
adjustHeap(arr, n, i);
}
// 交换堆顶元素和最后一个元素,并调整堆
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
adjustHeap(arr, i, 0);
}
}
int main() {
int arr[] = {91, 84, 72, 63, 55, 46, 37, 29, 20, 11};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```