选择排序---堆排序

二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足两个特性：

• 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值

• 每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
  当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：

  
  11B3620D-3236-4882-89D8-0E45CDA8A62D.png

堆的存储

一般都用数组来表示堆，i节点的父节点下标为（i-1)/2。它的左右子节点下标分别为2i+1和2i+2。如第0个节点左右子节点下标分别为1和2.

1A2BD5F2-D816-4846-A220-5C068D3C132C.png

java代码

public static void heapSort(int[] arr) {
        // 将待排序的序列构建成一个大顶堆
        for (int i = arr.length / 2; i >= 0; i--) {
            heapAdjust(arr, i, arr.length);
        }

        // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
            heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
        }
    }

    /**
     * 构建堆的过程
     *
     * @param arr 需要排序的数组
     * @param i   需要构建堆的根节点的序号
     * @param n   数组的长度
     */
    private static void heapAdjust(int[] arr, int i, int n) {
        int currentIndex = i;
        while (currentIndex <= n / 2 - 1) {
            int leftChildIndex = currentIndex * 2 + 1;
            int maxChildIndex = leftChildIndex;
            if (leftChildIndex < n - 1) {
                if (arr[leftChildIndex] < arr[leftChildIndex + 1]) {
                    maxChildIndex = leftChildIndex + 1;
                }
            }
            if (arr[currentIndex] < arr[maxChildIndex]) {
                int temp = arr[currentIndex];
                arr[currentIndex] = arr[maxChildIndex];
                arr[maxChildIndex] = temp;
                currentIndex = maxChildIndex;
            } else {
                break;
            }
        }
    }