堆排序算法的设计与分析
问题描述：设计并分析堆排序
【前置知识：什么是堆？】
堆（Heap）是一种特殊的树形数据结构，它满足以下两个条件之一：
- 最大堆（Max Heap）：
- 每个节点的值都大于或等于其子节点的值。
- 换句话说，根节点的值是整个堆中最大的。
- 最小堆（Min Heap）：
- 每个节点的值都小于或等于其子节点的值。
- 换句话说，根节点的值是整个堆中最小的。
堆的基本特点
- 完全二叉树：堆通常被实现为完全二叉树，也就是说，除了最后一层，所有层都是满的，而且最后一层的节点都是从左到右排列的。
- 堆的性质：对于最大堆，任意节点的值都大于或等于其子节点的值；对于最小堆，任意节点的值都小于或等于其子节点的值。
堆的操作
堆支持以下基本操作：
- 插入（Insert）：
- 在堆中插入一个新元素，首先将新元素放在堆的末尾，然后通过上浮操作使其恢复堆的性质。
- 删除（Delete）：
- 删除堆顶元素（最大堆的最大值或最小堆的最小值），用堆的最后一个元素替换堆顶元素，然后通过下沉操作使其恢复堆的性质。
- 堆化（Heapify）：
- 将一个无序数组调整为堆结构，可以通过自下而上的方法调整树的每个节点来实现。
堆的应用
堆有很多应用场景，包括但不限于：
- 优先队列（Priority Queue）：堆可以高效地实现优先队列，支持快速插入和删除操作。
- 堆排序（Heap Sort）：一种利用堆的性质进行排序的算法。
- 求中位数：使用两个堆（一个最大堆和一个最小堆）可以高效地求动态数据流的中位数。
【算法设计思想】
构建最大堆：
- 从无序数组构建一个最大堆。最大堆是指每个节点的值都大于或等于其子节点的值，这样堆顶元素（即数组的第一个元素）就是整个数组的最大值。
交换堆顶和堆的最后一个元素：
- 将堆顶元素（即最大值）和堆的最后一个元素交换，这样最大值就被放到数组的末尾，接下来只需对前面部分进行堆调整即可。
堆调整：
- 调整交换后的堆，使其再次成为最大堆。这个过程称为堆调整（Heapify），确保交换后的堆依然满足堆的性质。
重复步骤2和步骤3：
- 不断将堆顶元素和堆的最后一个元素交换，然后对前面的部分进行堆调整，直到所有元素都被排序。
【算法描述】
// 堆调整函数，维护最大堆性质
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，维护堆性质
heapify(arr, n, largest);
}
}
// 主函数，进行堆排序
void heapSort(int arr[], int n) {
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 一个个取出元素进行排序
for (int i = n - 1; i > 0; i--) {
// 将当前根节点移到末尾
swap(&arr[0], &arr[i]);
// 调整堆
heapify(arr, i, 0);
}
}
【完整的测试程序】
#include <stdio.h>
// 交换两个元素的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 堆调整函数，维护最大堆性质
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，维护堆性质
heapify(arr, n, largest);
}
}
// 主函数，进行堆排序
void heapSort(int arr[], int n) {
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 一个个取出元素进行排序
for (int i = n - 1; i > 0; i--) {
// 将当前根节点移到末尾
swap(&arr[0], &arr[i]);
// 调整堆
heapify(arr, i, 0);
}
}
// 打印数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// 测试堆排序
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组:\n");
printArray(arr, n);
heapSort(arr, n);
printf("排序后的数组:\n");
printArray(arr, n);
return 0;
}