堆排序可视化：https://visualgo.net/zh/heap

二叉树的链式存储

完全二叉树的链式存储：

  • 父结点索引为 n ，则其左右结点的索引分别为：
    • 左子结点索引：2*n + 1
    • 右子结点索引：2*n + 2
  • 子结点索引为 n，则其父结点的索引为：(n-1)/2 ，向下取整

image.png

堆结构

堆结构：堆是一种树结构，准确的说是一个完全二叉树，在此树中，每个节点对应于原始数据的一个记录，并且每个节点应该满足如下条件

  • 小根堆：如果结点按照从小到大的顺序排序，要求非叶子结点的数据要大于或等于其左右结点的数据
  • 大根堆：如果结点按照从大到小的顺序排序，要求非叶子结点的数据要小于或等于其左右结点的数据

堆的向下调整：假设结点的左右子树都是堆，但根结点不满足堆的性质，则可以通过一次向下的调整来将其变成一个堆
未命名绘图.png
实现：

  • 递归实现 ```java // 堆的向下调整：用于处理左右结点为大堆顶，而根结点不满足大堆顶性质时的调整 // len：数组中有效数据的长度 private static void heapify(int[] arr, int root, int len) { int left = 2 root + 1; int right = 2 root + 2;

    // 最大结点值的位置，初始化为根结点 int max = root;

    // 与左右结点进行比较，获取最大值 if (left < len && arr[max] < arr[left]) {

    1.   max = left;

    } if (right < len && arr[max] < arr[right]) {

    1.   max = right;

    }

    // 如果最大值为子结点，进行交换，并以交换后的子结点为根结点继续进行heapify if (max != root) {

    1.   swap(arr, root, max);
    2.   heapify(arr, max, len);

    } }

// 用于交换数组中两个位置的值 private static void swap(int[] arr, int i, int j) { arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }

  2. - 非递归实现：
  3. ```java
  4. // arr：待传入的数组
  5. // root：根结点的位置
  6. // len：传入数组的有效数据的长度
  7. private static void heapify(int[] arr, int root, int len) {
  8.     // 左子节点的位置
  9.     int left = root * 2 + 1;
  10.     // 最大值的索引
  11.     int maxIndex = root;
  13.     // 即存在左子结点的情况下不断循环
  14.     while (left < len) {
  15.         if (arr[left] > arr[maxIndex]) {
  16.             // 左子结点的值大于根结点，将最大值的索引指向左子结点
  17.             maxIndex = left;
  18.         }
  19.         if (left + 1 < len && arr[left + 1] > arr[maxIndex]) {
  20.             // 如果存在右子结点，&& 会进行短路，即 left + 1< len 不满足会直接跳过，不会导致出现数组越界异常
  21.             maxIndex = left + 1;
  22.         }
  24.         if (maxIndex == root) {
  25.             // 当根结点为最大结点，直接跳出循环
  26.             break;
  27.         } else {
  28.             // 将根结点与最大值结点的值进行交换
  29.             swap(arr, root, maxIndex);
  30.             // 将最大值的索引赋给根结点，开启新一轮判断
  31.             root = maxIndex;
  32.             left = root * 2 + 1;
  33.         }
  34.     }
  35. }

构建初始堆：

  • 从数组中的最后一个非叶子结点进行堆的向下调整，然后依次处理前面的非叶子结点

    1. // len：数组中有效位置的长度
    2. private static void build(int[] arr, int len) {
    3.   // 最后非叶子结点在数组中的索引
    4.   // 数组的有效长度为len，所以最后一个叶子结点的索引为len - 1
    5.   // 而最后一个叶子结点的父结点即为最后一个非叶子结点，计算该结点的索引(java默认向下取整)：(len-1-1)/2
    6.   int end = (len - 2) >> 1;
    8.   // 依次前推，对非叶子结点进行 heapify()
    9.   for (; end >= 0; end--) {
    10.       heapify(arr, end, arr.length);
    11.   }
    12. }

最大堆的出队操作：

  • 从堆头获取的为堆中元素的最大值，为了保持最大堆的性质，我们可以将堆尾元素填充到堆头，再对堆头元素进行一次向下调整，即能够恢复最大堆的性质

堆排序

将一个数组进行从小到大进行排序：

  • 先构建一个最大堆

  • 然后利用每次出堆都是从堆头进行出堆，从堆尾获取元素进行填充到堆头，可以直接将最大堆的堆头元素与堆尾元素进行交换，然后将队列中的有效长度减一，就能实现原地堆排序
    ```java public static void sort(int[] arr) { // 1、构建初始堆 build(arr, arr.length);

    // 2、依次将头结点移至堆尾后一位 int len = arr.length - 1; while (len > 0) {

    1.   swap(arr, 0, len);
    2.   heapify(arr, 0, len--);

    } }

// len：元素的数量 private static void build(int[] arr, int len) { int end = (len - 2) >> 1; for (; end >= 0; end—) { heapify(arr, end, arr.length); } }

// 堆的向下调整：用于处理左右结点为大堆顶，而根结点不满足大堆顶性质时的调整 // 数组的有效数据的长度 private static void heapify(int[] arr, int root, int len) { int left = 2 root + 1; int right = 2 root + 2;

  1. // 最大结点值的位置，初始化为根结点
  2. int max = root;
  3. if (left < len && arr[max] < arr[left]) {
  4.     max = left;
  5. }
  6. if (right < len && arr[max] < arr[right]) {
  7.     max = right;
  8. }
  10. // 如果最大值为子结点，进行交换，并以交换后的子结点为根结点继续进行heapify
  11. if (max != root) {
  12.     swap(arr, root, max);
  13.     heapify(arr, max, len);
  14. }

}

// 利用异或运算的性质进行元素交换 private static void swap(int[] arr, int i, int j) { arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; } ```