思路
堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值，被称为“大根堆”；或者每个节点的值都小于或等于其子节点的值，被称为“小根堆”。在堆排序中，我们使用的是大根堆，即根节点的值是最大的元素。
堆排序的基本思路是：
- 建立一个大根堆。将待排序的序列构建成一个大根堆，即所有非叶子节点的值都大于或等于其子节点的值。
- 交换堆顶元素和末尾元素。将堆顶元素与末尾元素进行交换，将最大值放在末尾位置。
- 调整堆。将剩余的元素重新构建成一个大根堆，重复执行步骤2和步骤3，直到整个序列有序。
具体地，我们可以将序列看成一个完全二叉树，将其转化为一个数组来处理。建立大根堆的过程可以使用“向下调整”来实现，具体步骤如下：
- 从最后一个非叶子节点开始，对每个节点进行***向下调整 * 操作。具体地，将当前节点的值与其左右子节点的值进行比较，如果当前节点的值小于左右子节点的值中的较大值，就将当前节点的值与左右子节点中的较大值进行交换，然后将指针移动到左右子节点中的较大值所在的位置，继续向下调整。
当我们将数组构建成一个大根堆之后，堆的根节点（也就是数组的第一个元素）一定是堆中的最大值。因此，我们将堆顶元素（即根节点）与堆中最后一个元素进行交换，这样最大值就被放在了数组的末尾位置。接着，我们将堆的范围缩小一位，即将堆的范围设为除去已经排好序的最后一个元素以外的其余元素，再重新调整堆，使得堆的根节点再次成为当前堆中的最大值。如此反复，直到堆的范围缩小到只剩一个元素，整个数组就被排好序了。
- 重复执行步骤1，直到所有的非叶子节点都被调整过一遍。
建立好大根堆后，我们就可以进行堆排序了。具体步骤如下：
-
将堆顶元素与末尾元素进行交换，将最大值放在末尾位置。
当堆是一个完全二叉树时，可以通过以下方式计算一个节点的父节点和左右子节点的位置：
- 父节点的位置：假设当前节点的位置是
i，那么它的父节点的位置为(i-1)/2。 - 左子节点的位置：假设当前节点的位置是
i，那么它的左子节点的位置为2i+1。 - 右子节点的位置：假设当前节点的位置是
i，那么它的右子节点的位置为2i+2。
需要注意的是，这种计算方式只适用于堆是一个完全二叉树的情况，如果堆不是一个完全二叉树，那么就需要使用其他的方式计算节点的位置。
- 父节点的位置：假设当前节点的位置是
-
缩小堆的范围，将剩余的元素重新构建成一个大根堆。
-
重复执行步骤1和步骤2，直到整个序列有序。
代码
,public static void heapSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 1. 建立大根堆
buildHeap(arr);
// 2. 交换堆顶元素和末尾元素，重建堆
int end = arr.length - 1;
while (end > 0) {
swap(arr, 0, end);
end--;
adjustHeap(arr, 0, end);
}
}
// 建立大根堆
private static void buildHeap(int[] arr) {
int parent = (arr.length - 2) / 2; // 最后一个非叶子节点的位置,即最后一个节点的父节点
for (int i = parent; i >= 0; i--) {
adjustHeap(arr, i, arr.length - 1);
}
}
// 调整堆
private static void adjustHeap(int[] arr, int parent, int end) {
int child = 2 * parent + 1; // 左子节点的位置
int temp = arr[parent]; // 当前节点的值
while (child <= end) {
// 选择左右子节点中的较大值
if (child + 1 <= end && arr[child] < arr[child + 1]) {
child++;
}
// 如果当前节点的值小于左右子节点的较大值，则进行交换
if (temp < arr[child]) {
arr[parent] = arr[child];
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
arr[parent] = temp;
}
// 交换数组中的两个元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
- 为什么adjustHeap()函数最后需要调用arr[parent] = temp
- 在
adjustHeap()函数中，我们将堆顶元素和堆的最后一个元素进行交换，然后调整堆使其重新成为大根堆。在调整堆的过程中，我们将堆顶元素向下移动，将其与其左右子节点中较大的那个节点进行比较，如果比该节点小，就将该节点上移，直到不再小于其子节点为止。 - 当我们找到了堆顶元素的合适位置之后，我们需要将其放到该位置上。但是此时，堆顶元素的值已经被赋给了某个子节点，原本存储堆顶元素的位置已经被占据了。为了将堆顶元素放到正确的位置上，我们需要将其存储到堆顶元素原本所在的位置上。
- 具体而言，
arr[parent] = temp;这句话的作用是将堆顶元素（即原本存储在parent位置上的元素）的值替换成temp，这样就可以将堆顶元素放到正确的位置上了。
- 为什么arr[parent] = temp被放在了while循环外面呢
- 将
arr[parent] = temp;这段代码放在while循环内部是没有问题的，因为它只是将堆顶元素存储到正确的位置上，不会对堆的调整造成影响。但是，将其放在循环外面可以更清晰地表达代码的意图，也可以避免重复的赋值操作。 - 具体而言，当
while循环结束时，我们已经找到了堆顶元素的正确位置，此时的parent指向的就是该位置。因此，在循环外面执行arr[parent] = temp;语句，将堆顶元素存储到parent位置上，就可以完成堆的调整了。 - 如果将其放在循环内部，那么每次循环都要执行一次
arr[parent] = temp;语句，这样就会造成不必要的赋值操作。因此，将其放在循环外面可以避免这个问题，同时也更清晰地表达代码的意图。
堆排序扩展题目
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
思路
java中的PriorityQueue用的小根堆
import java.util.PriorityQueue;
public class SortAlmostSortedArray {
public static void sort(int[] arr, int k) {
// 创建一个小根堆，存放当前窗口内的元素
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 遍历数组，将元素加入小根堆中，如果堆中的元素数量超过了 k，就将堆顶元素弹出
for (int i = 0; i < arr.length; i++) {
// 将当前元素加入小根堆
minHeap.offer(arr[i]);
// 如果堆中的元素数量超过了 k，就将堆顶元素弹出并放入结果数组中
if (minHeap.size() > k) {
arr[i - k] = minHeap.poll();
}
}
// 将剩余的元素按顺序依次放入结果数组中
while (!minHeap.isEmpty()) {
arr[arr.length - minHeap.size()] = minHeap.poll();
}
}
public static void main(String[] args) {
int[] arr = {6, 5, 3, 2, 8, 10, 9};
int k = 3;
System.out.println("Before sorting -> "+Arrays.toString(arr));
sort(arr, k);
System.out.println("After sorting -> "+Arrays.toString(arr));
}
}