目录
1、什么是堆
2、大顶堆
3、小顶堆
4、排序思想：
5、代码实现
1、什么是堆
在计算机科学中，堆（Heap）是一种特殊的数据结构，通常是一个可以被看作近似完全二叉树的数组对象。在堆中，父节点的值总是大于或等于子节点的值（大顶堆），或者父节点的值总是小于或等于子节点的值（小顶堆）。
堆分为两种主要类型：
2、大顶堆
在大顶堆中，父节点的值大于或等于其任何一个子节点的值。因此，堆的根节点包含的是整个堆中的最大值。
3、小顶堆
在小顶堆中，父节点的值小于或等于其任何一个子节点的值。因此，堆的根节点包含的是整个堆中的最小值。
堆常常用于实现优先队列和堆排序等算法。堆排序正是利用堆的特性进行的一种排序算法。
堆的特点：
- 堆是一个完全二叉树，即除了最后一层，其他层的节点都是满的，最后一层的节点尽量靠左排列。
- 在堆中，父节点和子节点之间存在特定的大小关系，满足堆的性质。
堆的操作包括插入（将新元素添加到堆中）和删除（从堆中移除某个元素）。这两个操作会触发堆的调整，以保持堆的结构和性质。
在实现上，堆通常以数组的形式存储，可以通过数组索引的关系来找到父节点和子节点。这种数组表示法使得堆的操作更加高效。
4、排序思想：
它的排序思想主要分为两个步骤：
1、构建堆；
2、排序；
构建堆：
- 首先，将待排序的数组看作是一个完全二叉树，并从最后一个非叶子节点开始向前遍历。
- 对于每个节点，进行一次“堆化”操作，即将当前节点与其子节点比较，如果当前节点的值小于（或大于，取决于是小顶堆还是大顶堆）子节点的值，则交换它们的位置。
- 重复这个过程，直到整个数组变成一个满足堆性质的堆。这一步的时间复杂度为O(n)，其中n是数组的长度。
排序：
- 构建好堆之后，堆顶元素是最大值（大顶堆）或最小值（小顶堆）。
- 将堆顶元素与堆的最后一个元素交换位置，然后将剩余元素重新调整为堆，除了最后一个元素，其余部分仍然保持堆的性质。
- 重复上述步骤，每次将堆中最大（或最小）的元素放到数组的末尾，直到整个数组有序。
堆排序的关键在于构建和调整堆的过程。构建堆的时间复杂度是O(n)，排序阶段进行n-1次交换和堆调整，每次的时间复杂度是O(log n)。因此，堆排序的总体时间复杂度是O(n log n)，其中n是数组的长度。
堆排序是一种原地排序算法，不需要额外的辅助数组。它的优点在于对于大规模数据集的排序比较高效，但缺点是相对于一些其他排序算法，它对于小规模数据集的性能可能不如其他算法。此外，堆排序是不稳定的排序算法。
5、代码实现
public class HeapSort {
public static void heapSort(int[] array) {
int n = array.length;
// 构建大顶堆
buildMaxHeap(array, n);
// 排序
for (int i = n - 1; i > 0; i--) {
// 将堆顶元素（最大值）与数组末尾元素交换
swap(array, 0, i);
// 重新调整堆，排除已排序的部分
maxHeapify(array, i, 0);
}
}
// 构建大顶堆
private static void buildMaxHeap(int[] array, int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(array, n, i);
}
}
// 堆调整，使得以i为根节点的子树满足大顶堆的性质
private static void maxHeapify(int[] array, int n, int i) {
int largest = i; // 初始化父节点为最大值
int leftChild = 2 * i + 1; // 左子节点
int rightChild = 2 * i + 2; // 右子节点
// 找出左右子节点中的最大值
if (leftChild < n && array[leftChild] > array[largest]) {
largest = leftChild;
}
if (rightChild < n && array[rightChild] > array[largest]) {
largest = rightChild;
}
// 如果最大值不是父节点，则交换它们的位置并继续调整
if (largest != i) {
swap(array, i, largest);
maxHeapify(array, n, largest);
}
}
// 交换数组中两个元素的位置
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 测试堆排序
public static void main(String[] args) {
int[] array = {4, 10, 3, 5, 1};
System.out.println("Original Array: " + Arrays.toString(array));
heapSort(array);
System.out.println("Sorted Array: " + Arrays.toString(array));
}
}
这段代码首先调用 buildMaxHeap 构建初始的大顶堆，然后进行堆排序，最终得到一个有序数组。 maxHeapify 方法用于在堆排序中调整堆的结构，确保它仍然满足大顶堆的性质。
