堆

堆结构就是用数组实现的完全二叉树结构

完全二叉树的性质，对于节点 i 来说：

i 的左节点下标：
i 的右节点下标：
i 的父节点下标：
1. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
2. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
3. 堆结构的 heapInsert 与 heapify 操作
4. 堆结构的增大和减少 ```java /**
- 某数出现在 index 位置，是否能继续往上移动
- 思路：维护大根堆，如果当前数大于父节点，就交换位置
- @param arr
- @param index */ public static void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } }

/**

堆化，某个数在 index 位置，能否往下移动
思路：
把在 index 位置的数以及它的左右子节点去最大值，如果最大值！= 该数，
就交换俩数位置直到最大值 == 该数或者不存在子节点停止
典型场景：
在堆中去掉下标为 index 的节点，此时可以数组将末尾的数放到 index 上，并且做 heapify 操作来维持堆结构 *
@param arr
@param index

@param heapSize / public static void heapify(int[] arr, int index, int heapSize) { // 左子节点 int left = index 2 + 1;

while (left < heapSize) {// 下面还有子节点

 // 右子节点
 int right = left + 1;
 // 在两个子节点间，谁的值大，把下标给 largest
 int largest = right < heapSize && arr[right] > arr[left] ? right : left;
 // 父节点和子节点间，谁的值大，把下标给 largest
 largest = arr[largest] > arr[index] ? largest : index;
 if (largest == index) break;
 swap(arr, largest, index);
 index = largest;
 left = index * 2 + 1;

} } ``` 对 index 处做修改：

如果变大，做 heapInsert 操作
如果变小，做 heapify 操作
如果不知道变化的情况，对该数一次做 heapInsert 、heapify 也可以维持堆结构
复杂度都是

优先级队列结构，就是堆结构

堆排序

思路：

先让整个数组都变成大根堆结构，建立堆的过程：
1. 从上到下的方法，时间复杂度为
2. 从下到上的方法，时间复杂度为
把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始,时间复杂度为
堆的大小减小成0之后，排序完成 ```java import java.util.Arrays;

public class HeapSort {

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 逐个插入到数组中
    for (int i = 0; i < arr.length; i++) { // O(N)
        heapInsert(arr, i); // O(logN)
    }
    int heapSize = arr.length;
    // 将堆顶（最大值）放到末尾，然后让末尾数字 heapify，维持大根堆，然后继续取堆顶
    swap(arr, 0, --heapSize);
    while (heapSize > 0) { // O(N)
        heapify(arr, 0, heapSize); // O(logN)
        swap(arr, 0, --heapSize); // O(1)
    }
}

public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

public static void heapify(int[] arr, int index, int heapSize) {
    // 左子节点
    int left = index * 2 + 1;

    while (left < heapSize) {// 下面还有子节点
        // 右子节点
        int right = left + 1;
        // 在两个子节点间，谁的值大，把下标给 largest
        int largest = right < heapSize && arr[right] > arr[left] ? right : left;
        // 父节点和子节点直接，谁的值大，把下标给 largest
        largest = arr[largest] > arr[index] ? largest : index;

        if (largest == index) break;

        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

private static void swap(int[] arr, int i, int j) {
    if (arr[i] == arr[j]) return;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

public static void main(String[] args) {
    int[] arr = ArrayGenerator.getArr(10, 50);
    System.out.println(Arrays.toString(arr));
    heapSort(arr);
    System.out.println(Arrays.toString(arr));
    for (int i = 0; i < 50; i++) {
        arr = ArrayGenerator.getArr(10, 50);
        int[] arr1 = ArrayGenerator.getSortArr(arr);
        heapSort(arr);
        if (!ArrayGenerator.isSame(arr, arr1)) {
            System.out.println("出错了："+Arrays.toString(arr));
        }
    }
}

}

时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/bac8d392664b06fc724fb542d50ad111.svg#card=math&code=O%28N%20%5Ccdot%20%5Clog%20N%29&height=20&id=aZX0j) ，这个算法还有优化空间，`heapInsert` 和 `heapify` 都能堆化数组，但是在数组最开始被堆化时使用 `heapify` 会更快一点，复杂度为 ![](https://cdn.nlark.com/yuque/__latex/33697ce7dfa48ba80980d298c8089378.svg#card=math&code=O%28N%29&height=20&id=gQH3Q)（证明略……），也就是说整个`heapSort` 方法可以被优化为：
```java
public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 逐个插入到数组中
    //        for (int i = 0; i < arr.length; i++) {
    //            heapInsert(arr, i);
    //        }
    // 优化后：
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
    int heapSize = arr.length;
    // 将堆顶（最大值）放到末尾，然后让末尾数字 heapify，维持大根堆，然后继续取堆顶
    swap(arr, 0, --heapSize);
    while (heapSize > 0) {
        heapify(arr, 0, heapSize);
        swap(arr, 0, --heapSize);
    }
}

这样只需要 heapify 就能做对排序，对比原先肯定是快了一点，但是也影响不大，毕竟只是做了一步优化且整体的时间复杂度依旧为堆排序 - 图8

算法应用

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过 k，些且 k 相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

Java 中的 **PriorityQueue** 优先级队列就是使用堆实现，默认为小根堆

思路：
每个元素移动的距离可以不超过 k，可以构造一个 heapSize 为 k 的小根堆，每次取堆顶放到数组中

import java.util.PriorityQueue;

public class SortArrayDistanceLessK {
    public void sortArrayDistanceLessK(int[] arr, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // 放 k-1 个数
        for (int i = 0; i < Math.min(arr.length, k); i++) {
            heap.add(arr[i]);
        }

        // 放第 k 个数进去，每次取堆顶就是最小值
        int i = 0;
        for (; i < arr.length; i++) {
            heap.add(arr[i]);
            arr[i] = heap.poll();
        }

        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }
}