二叉堆-堆排序

一 ：理解基础概念 1. 堆排序的基本概念

堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的排序算法。它的核心思想是通过构建一个最大堆或最小堆，利用堆的性质逐步将堆顶元素（最大值或最小值）取出，从而实现排序。

二叉堆：

二叉堆是一种完全二叉树（Complete Binary Tree），即除了最后一层，其他层都是满的，且最后一层的节点尽可能靠左排列。二叉堆分为两种： 最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值。堆顶元素是最大值。最小堆（Min Heap）：每个节点的值都小于或等于其子节点的值。堆顶元素是最小值。

堆排序的核心思想：

将待排序的数组构建成一个最大堆（或最小堆）。将堆顶元素（最大值或最小值）与堆的最后一个元素交换，然后将堆的大小减一。对剩余的堆进行调整，使其重新满足堆的性质。重复上述步骤，直到堆的大小为 1，排序完成。

---

2. 二叉堆的性质

二叉堆的性质是堆排序的基础，理解这些性质是掌握堆排序的关键。

最大堆的性质 每个节点的值都大于或等于其子节点的值。堆顶元素是堆中的最大值。示例： 10 / \ 7 8 / \ / 5 6 3 在这个最大堆中，每个父节点的值都大于其子节点的值。 最小堆的性质 每个节点的值都小于或等于其子节点的值。堆顶元素是堆中的最小值。示例： 1 / \ 2 3 / \ / 4 5 6 在这个最小堆中，每个父节点的值都小于其子节点的值。 3. 堆的数组表示

由于堆是完全二叉树，因此可以用数组来表示堆。这种表示方法不仅节省空间，还能方便地通过索引访问父节点和子节点。

数组表示规则 对于一个节点 i（数组中的索引，从 0 开始）： 父节点：(i - 1) / 2左子节点：2 * i + 1右子节点：2 * i + 2 示例

假设有一个数组 [10, 7, 8, 5, 6, 3]，它表示一个最大堆：

索引: 0 1 2 3 4 5 值: 10 7 8 5 6 3

对应的堆结构：

10 (0) / \ 7 (1) 8 (2) / \ / 5(3)6(4)3(5) 验证父子节点关系： 节点 1（值 7）的父节点是 (1 - 1) / 2 = 0（值 10）。节点 2（值 8）的父节点是 (2 - 1) / 2 = 0（值 10）。节点 0（值 10）的左子节点是 2 * 0 + 1 = 1（值 7），右子节点是 2 * 0 + 2 = 2（值 8）。

---

4. 堆排序的关键操作

堆排序的核心操作包括：

构建堆（Heapify）：

将一个无序数组调整为一个最大堆或最小堆。从最后一个非叶子节点开始，逐步向上调整每个子树，使其满足堆的性质。

调整堆（Sift Down 或 Sift Up）：

Sift Down：从某个节点开始，向下调整子树，使其满足堆的性质。Sift Up：从某个节点开始，向上调整子树，使其满足堆的性质。

排序：

将堆顶元素与堆的最后一个元素交换，然后将堆的大小减一。对剩余的堆进行调整，使其重新满足堆的性质。重复上述步骤，直到堆的大小为 1。

---

二. 堆的构建（Heapify）

堆化（Heapify）是将一个无序数组调整为堆的过程。堆化的核心思想是从最后一个非叶子节点开始，逐步调整每个子树，使其满足堆的性质（最大堆或最小堆）。

堆化的步骤： 找到最后一个非叶子节点： 最后一个非叶子节点的索引为 (n / 2) - 1，其中 n 是数组的长度。 从后向前调整： 从最后一个非叶子节点开始，向前依次调整每个节点。对每个节点，检查其是否满足堆的性质。如果不满足，则向下调整（Sift Down）。 示例：

假设有一个数组 [4, 10, 3, 5, 1]，我们需要将其构建为最大堆：

最后一个非叶子节点的索引是 (5 // 2) - 1 = 1（值 10）。从索引 1 开始向前调整： 调整节点 1（值 10），其子树已经满足最大堆性质。调整节点 0（值 4），其左子节点 10 大于 4，交换两者。调整后的数组为 [10, 5, 3, 4, 1]。

---

2. 实现堆化操作

堆化操作可以通过递归或迭代实现。以下是最大堆的堆化实现（以 java为例）：

public class Heapify { // 堆化操作，将数组调整为最大堆 public static 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) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // 递归堆化受影响的子树 heapify(arr, n, largest); } } // 构建最大堆 public static void buildMaxHeap(int[] arr) { int n = arr.length; // 从最后一个非叶子节点开始，向前遍历 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } } // 打印数组 public static void printArray(int[] arr) { for (int i : arr) { System.out.print(i + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = {4, 10, 3, 5, 1}; System.out.println("原始数组:"); printArray(arr); // 构建最大堆 buildMaxHeap(arr); System.out.println("最大堆数组:"); printArray(arr); } }

---

3. 插入和删除操作

堆的插入和删除操作是堆数据结构的基本操作，分别通过“上浮”和“下沉”来维护堆的性质。

插入操作： 将新元素添加到堆的末尾。对新元素进行“上浮”操作，使其满足堆的性质。 上浮（Sift Up）实现： /** * 插入操作（插入末尾），通过上浮（Sift Up）实现 */ private static void siftUp(List<Integer> arr, int i) { while (i > 0) { // 父节点索引 int parent = (i - 1) / 2; if(arr.get(parent) < arr.get(i)) { // 交换当前节点和父节点 Integer temp = arr.get(parent); arr.set(parent, arr.get(i)); arr.set(i, temp); // 继续上浮 i = parent; } } } 删除操作： 删除堆顶元素（最大值或最小值）。将堆的最后一个元素移到堆顶。对堆顶元素进行“下沉”操作，使其满足堆的性质。 下沉（Sift Down）实现： /** * 取出堆顶元素，并重新排序 * @param arr * @return */ private static Integer getHeapUp(List<Integer> arr) { Integer heapUpNumber = arr.get(0); arr.set(0, arr.get(arr.size() - 1)); arr.remove(arr.size() - 1); System.out.println("取出堆顶元素后的集合："); printArray(arr); siftDown(arr, arr.size(), 0); return heapUpNumber; } /** * 下沉（Sift Down）实现 */ private static void siftDown(List<Integer> arr, int length, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if(left < length && arr.get(left) > arr.get(largest)) { largest = left; } if(right < length && arr.get(right) > arr.get(largest)) { largest = right; } if(largest != i) { int swap = arr.get(i); arr.set(i, arr.get(largest)); arr.set(largest, swap); siftDown(arr, length, largest); } }

---

三：实现堆排序

堆排序的核心思想是利用最大堆的性质，逐步将堆顶元素（最大值）取出并放到数组的末尾，最终得到一个有序数组:

将堆顶元素（最大值）与堆的最后一个元素交换。将堆的大小减一（即排除已排序的部分）。对剩余的堆进行调整，使其重新满足最大堆的性质。重复上述步骤，直到堆的大小为 1。 import java.util.Arrays; public class HeapSort { /** * 将数组 arr 的索引 i 的子树调整为最大堆。 * * @param arr 待调整的数组 * @param n 堆的大小 * @param i 当前节点的索引 */ private static 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) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); // 递归调整子树 } } /** * 对数组 arr 进行堆排序。 * * @param arr 待排序的数组 */ public static void heapSort(int[] arr) { int n = arr.length; // 1. 构建最大堆 // 从最后一个非叶子节点开始，向前依次调整 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 2. 排序 // 将堆顶元素（最大值）与堆的最后一个元素交换，然后调整剩余堆 for (int i = n - 1; i > 0; i--) { // 交换堆顶和最后一个元素 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 调整剩余堆 heapify(arr, i, 0); } } /** * 测试堆排序 */ public static void testHeapSort() { // 测试用例 int[][] testCases = { {4, 10, 3, 5, 1}, // 普通数组 {1, 2, 3, 4, 5}, // 已经有序的数组 {5, 4, 3, 2, 1}, // 逆序数组 {}, // 空数组 {1}, // 单个元素的数组 {3, 3, 3, 3, 3} // 所有元素相同的数组 }; for (int[] arr : testCases) { System.out.println("排序前: " + Arrays.toString(arr)); heapSort(arr); System.out.println("排序后: " + Arrays.toString(arr)); System.out.println("---------------------"); } } /** * 性能测试 */ public static void performanceTest() { int[] sizes = {1000, 10000, 100000}; // 不同规模的数组 for (int size : sizes) { int[] arr = generateLargeArray(size); long startTime = System.currentTimeMillis(); heapSort(arr); long endTime = System.currentTimeMillis(); System.out.printf("数组大小: %d, 排序耗时: %d 毫秒\n", size, endTime - startTime); } } /** * 生成大规模随机数组 * * @param size 数组大小 * @return 随机数组 */ private static int[] generateLargeArray(int size) { int[] arr = new int[size]; for (int i = 0; i < size; i++) { arr[i] = (int) (Math.random() * 100000); } return arr; } public static void main(String[] args) { // 测试堆排序 testHeapSort(); // 性能测试 performanceTest(); } }

---

---

解决力扣（LeetCode）上的堆排序相关问题： 215. 数组中的第K个最大元素912. 排序数组

---