堆结构与堆排序

数组中前缀范围与完全二叉树的对应

数组的前缀范围可以与完全二叉树基本对应，以额外变量size来控制范围：

堆结构

堆可以认为是在数组上的，规定好组织方式的完全二叉树。

大根堆：任何一个子结构都应满足最大值在顶部
小根堆：任何一个子结构都应满足最小值在顶部

heapInsert（向上调整）

heapInsert是将新插入元素做调整以保证大根堆特性的过程。

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

heapify（向下调整）

heapify是将新变动元素做调整以保证大根堆特性的过程。

public static void heapify(int i, int size) {
        int l = i * 2 + 1;
        while (l < size) {
            int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
            best = arr[best] > arr[i] ? best : i;
            if (best == i) {
                break;
            }
            swap(best, i);
            i = best;
            l = i * 2 + 1;
        }
    }

若只有单侧孩子且值大于当前值，则直接认为单侧孩子是最大的，与当前元素做交换。

时间复杂度分析

不管一个结点怎么调整，都只与自己所在的那一条树枝有关，节点数为N的完全二叉树高度为向上取整，所以以上两个过程的时间复杂度均为这与完全二叉树本身结构也有关。

堆排序

堆排序的过程如下:

按照构建大根堆的方式，将待排序数组中的每个元素加入大根堆，每次size++
大数归位阶段：将上面步骤中的根节点（最大元素）与最后一个（数组）下标的元素交换，size--，即之后这个最大元素被排除出堆的范围，不参与堆调整
由于最小元素被移至堆顶，需要执行heapify过程将其向下移动，保证大根堆特征
循环执行上述过程，直至size==0

public static void heapSort1() {
        for (int i = 0; i < n; i++) {
            heapInsert(i);
        }
        int size = n;
        while (size > 1) {
            swap(0, --size);
            heapify(0, size);
        }
    }