一、先解答上次的思考题对树10,7,15,3,9,12,18删除 15 后中序3 7 9 10 12 18再删除 7 后中序3 9 10 12 18二、今天学习目标什么是堆、大顶堆、小顶堆堆的结构用数组存完全二叉树核心操作上浮、下沉堆实现优先队列完整代码三、什么是堆Heap堆是一棵满足堆序性质的完全二叉树通常用数组存储。两种常用堆大顶堆父节点 ≥ 左右孩子堆顶是最大值小顶堆父节点 ≤ 左右孩子堆顶是最小值特点结构是完全二叉树可以用数组高效存储取最值极快O (1)插入 / 删除O (log n)四、数组存储完全二叉树下标规律对于下标i从 0 开始左孩子2*i 1右孩子2*i 2父节点(i - 1) / 2五、核心操作下沉向下调整以大顶堆为例如果某个节点比孩子小就和较大的孩子交换一直往下沉直到满足堆性质。// 大顶堆下沉调整 void siftDown(int arr[], int n, int i) { while (1) { int maxPos i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[maxPos]) maxPos left; if (right n arr[right] arr[maxPos]) maxPos right; if (maxPos i) break; // 交换 int temp arr[i]; arr[i] arr[maxPos]; arr[maxPos] temp; i maxPos; } }六、建堆 堆实现优先队列取堆顶完整可运行代码#include stdio.h // 下沉调整大顶堆 void siftDown(int arr[], int n, int i) { while (1) { int maxPos i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[maxPos]) maxPos left; if (right n arr[right] arr[maxPos]) maxPos right; if (maxPos i) break; int temp arr[i]; arr[i] arr[maxPos]; arr[maxPos] temp; i maxPos; } } // 建堆 void buildHeap(int arr[], int n) { // 从最后一个非叶子节点往前建堆 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, n, i); } } // 删除堆顶取最大值 int deleteMax(int arr[], int *n) { int maxVal arr[0]; // 最后一个元素放到堆顶 arr[0] arr[*n - 1]; (*n)--; siftDown(arr, *n, 0); return maxVal; } // 测试 int main() { int arr[] {3, 1, 7, 9, 4, 2, 8}; int n sizeof(arr) / sizeof(arr[0]); buildHeap(arr, n); printf(依次取出堆顶大顶堆); while (n 0) { printf(%d , deleteMax(arr, n)); } return 0; }七、运行结果依次取出堆顶大顶堆9 8 7 4 3 2 1八、堆的典型用途优先队列任务调度、定时器堆排序O (n log n) 稳定高效TopK 问题找最大 / 最小的 k 个数九、今日小练习把数组[5, 2, 8, 1, 3]建成大顶堆依次取出堆顶观察输出是否降序