堆（二插堆）

一、堆的基本概念堆是一种基于完全二叉树的数据结构并且满足堆序性质大顶堆大根堆任意父节点的值 ≥ 子节点的值堆顶为最大值。小顶堆小根堆任意父节点的值 ≤ 子节点的值堆顶为最小值。特点逻辑上是一棵完全二叉树物理上可以用数组顺序存储不要求中序有序只要求父子有序常用于排序、优先队列、TOP-K 问题等二、堆的节点下标计算公式数组从 0 开始对于数组中任意下标为i的节点左孩子下标child_left 2 * i 1右孩子下标child_right 2 * i 2父节点下标parent (i - 1) / 2整数除法最后一个非叶子节点数组长度为n时最后一个非叶子节点下标last_non_leaf (n - 2) / 2堆排序建堆时就是从这个位置自底向上调整。三、堆排序核心思路构建大顶堆从最后一个非叶子节点开始向上逐个执行向下调整使整个数组满足堆性质。交换堆顶与末尾元素将堆顶最大值放到数组末尾确定一个元素的最终位置。重新调整堆结构排除已排好的末尾元素对新堆顶再次向下调整重复上述步骤直到整个数组有序。四、时间复杂度建堆O(n)排序每次调整 O (log n)共 n 次 →O(n log n)整体时间复杂度O(n log n)空间复杂度O(1)原地排序堆排序不依赖数据初始顺序最好、最坏、平均复杂度都是O(n log n)。五、总结堆 完全二叉树 堆序性质数组存储下标公式是核心堆排序 建堆 交换堆顶 向下调整高效稳定的排序算法时间复杂度 O (n log n)原地排序堆排序实现从小到大的排序 用大堆void Heapsort(int* arr, int n) { for (int i (n - 1 - 1) / 2; i 0; i--) {//从最下面的节点开始进行调整让后向上继续调整 int parent i; int child parent * 2 1; while (child n) { if ((child 1 n) arr[child] arr[child 1]) { child; } if (arr[child] arr[parent]) { swap(arr[child], arr[parent]); parent child; child parent * 2 1; } else { break; } } } int end n - 1; while (end 0) {//每次交换后我们要重新向下调整 swap(arr[0], arr[end]); int parent 0;//从第一个开始 int child parent * 2 1; while (child end) { if ((child 1 end) arr[child] arr[child 1]) { child; } if (arr[child] arr[parent]) { swap(arr[child], arr[parent]); parent child; child parent * 2 1; } else { break; } } end--;//当前最后一个值成为最大值 } }