完全二叉树

arr[i]的左孩子是arr[2*i+1]
arr[i]的右孩子是arr[2*i+2]
arr[i]的父结点时arr[(i-1)/2]

堆结构

1）堆结构就是用数组实现的完全二叉树结构
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4）堆结构的heapInsert与heapify操作
5）堆结构的增大和减少
6）优先级队列结构，就是堆结构

HeapInsert操作

// arr[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;
    }
}

Heapify操作

// arr[index]位置的数，能否往下移动
public static void heapify(int[] arr, int index, int heapSize) {
    int left = index * 2 + 1; // 左孩子的下标
    while (left < heapSize) { // 下方还有孩子的时候

        // 两个孩子中，谁的值大，把下标给largest
        // 1）只有左孩子，left -> largest
        // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
        // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // 父和较大的孩子之间，谁的值大，把下标给largest
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

建堆1(从顶到下)

for (int i = 0; i < arr.length; i++) { // O(N)
    heapInsert(arr, i); // O(logN)
}

时间复杂度O(N*logN)

建堆的Heapify的过程中，堆的高度在增加，所以每次Heapify的时间的复杂度是变化的，但是可以证明，Heapify的时间复杂度是O(N*logN)。

夹逼定理证明

假如2N个元素做Heapify形成堆，对于前N个元素的时间复杂度，由于平均堆高度小于logN，所以时间复杂度上限是O(NlogN), 对于后N个元素的时间复杂度，由于平均堆高度大于logN，所以时间复杂度的下限是O(N*logN)。

建堆2(从下到顶)

for (int i = arr.length - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
}

时间复杂度 O(N)

叶节点的数量级是N/2，倒数第二层的数量级N/3
T(N) = N/2 1 + N/4 2 + N/8 3 ….
2T(N) = N 1 + N/2 2 + N/4 3 ….
T(N) = N + N/2 + N/4 …. = O(N)。

从上往下，大量的结点做heapify时复杂度很高。
从下往上，大量的结点做heapify时复杂度较低。

堆排序

1，先让整个数组都变成大根堆结构，建立堆的过程:
1)从上到下的方法，时间复杂度为O(N x logN)
2)从下到上的方法，时间复杂度为O(N)
2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N * logN)
3，堆的大小减小成0之后，排序完成

// 堆排序额外空间复杂度O(1)
public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // O(N*logN)
//        for (int i = 0; i < arr.length; i++) { // O(N)
//            heapInsert(arr, i); // O(logN)
//        }
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    // O(N*logN)
    while (heapSize > 0) { // O(N)
        heapify(arr, 0, heapSize); // O(logN)
        swap(arr, 0, --heapSize); // O(1)
    }
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

相关题

leetcode :

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 大顶堆(从下向上建 o(longn))
        for (int i = nums.length-1; i >=0; i--){
            heapify(nums,i,nums.length);
        }
        // // 大顶堆(从上往下建 o(nlogn))
        // for (int i = 0; i < nums.length; i++){
        //     heapinsert(nums,i);
        // }
        int heapSize = nums.length;
        // 排序: 拿出堆顶，再修复堆结构。
        while(heapSize > 0){
            swap(nums,0,--heapSize);
            heapify(nums,0,heapSize);
        }
        // topk
        return nums[nums.length-k];
    }

    public static void heapify(int[] arr,int idx,int heapSize){
        // 往下放
        int left = idx * 2 + 1;
        while(left < heapSize){
            int largestChildIdx = left+1 < heapSize && arr[left+1] > arr[left] ? left+1 : left;
            if (arr[largestChildIdx] <= arr[idx]){
                break;
            }
            swap(arr,largestChildIdx,idx);
            idx = largestChildIdx;
            left = idx * 2 + 1;
        }
    }
    public static void heapinsert(int[] arr,int idx){
        // 往上放
        while(arr[idx] > arr[(idx-1)/2]){ // 
            swap(arr,idx,(idx-1)/2);
            idx = (idx-1)/2;
        }
    }

    public static void swap(int[] arr,int i,int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

作者：panda2025
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/by-panda2025-ug0p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法体系

7、堆结构、堆排序