堆排序

数据结构与算法

一、堆排序，数组升序排列

leetcode 912. 排序数组

用堆进行排序，需要将数组建为大根堆，堆顶就是最大的元素，然后每次取出大根堆的堆顶，依次从数组的最后一个元素往前进行交换，交换完成之后还需要重新调整堆，最终数组有序。

注意，建成堆之后数组只是大体有序，并不是全局有序，所以不能直接认为建一个小根堆就完事了，一次建堆就是将数组变为大体有序的过程，从这个角度来看，堆排序也是插入排序的一种优化思路。

public class Solution {
    public int[] sortArray(int[] nums) {
        buildHeap(nums);
        // 建完堆之后取出堆顶元素，和数组末位i的位置交换，重新调整堆
        int len = nums.length - 1;
        for (int i = len; i >= 1; i--) {
            swarp(nums, i, 0);
            len--;
            adjust(nums, 0, len);
        } 
        return nums;
    }
    private void buildHeap(int[] nums) {
        // 这里必须从底层往上调整，简单做法是从最后一个节点往上调整，但实际上只要对有孩子的节点从下往上调整即可
        for (int i = nums.length/2; i >= 0; i--) {
            adjust(nums, i, nums.length - 1);
        }
    }
    // 数组中指定长度建堆
    private void adjust(int[] nums, int i, int len) {
        int right = (i + 1) * 2;
        int left = right - 1;
        int maxIndex = i;
        if (left <= len && nums[left] >= nums[i]) {
            maxIndex = left;
        }
        if (right <= len && nums[right] >= nums[maxIndex]) {
            maxIndex = right;
        }
        if (maxIndex == i) {
            return;
        }
        swarp(nums, i , maxIndex);
        adjust(nums, maxIndex, len);
    }
    public void swarp(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

二、小根堆

剑指 Offer II 076. 数组中的第 k 大的数字

寻找数组中第k大的数，可以用一个大小为k的小根堆，让小根堆的根节点是最小的，先构建大小为k的小根堆，然后让剩余元素和根节点比较，如果比根节点还小，可以直接抛弃，不需要入堆，如果比根节点大，那么就用这个元素替换根节点，然后调整小根堆，调整的过程是让根节点和左右孩子节点总计三个节点中最小的那一个上浮，所以每次都要找到最小的节点，然后和根节点交换，如果发现最小的那个就是根节点，说明调整已经结束。

用数组来存储二叉树，小标为i的节点的有右孩子是(i+1)*2,左孩子下标就是右孩子减1

// k > 1 && k < nums.length
public class Solution {
    int[] heap = null; // 小根堆
     public int findKthLargest(int[] nums, int k) {
        heap = new int[k];
        // 先将k个元素入堆，然后再调整，不要边入堆边调整
        for (int i = 0; i < k; i++) {
            heap[i] = nums[i];
        }
        // 建堆
        buildHeap();
        for (int i = k; i < nums.length; i++) {
            setRoot(nums[i]);
        }
        return heap[0];
     }
     private void setRoot(int ver) {
        // 如果比根节点还小，就不用入堆了
        if (ver <= heap[0]) {
            return;
        }
        heap[0] = ver;
        adjust(0);
     }
     private void buildHeap() {
        // 这里必须从底层往上调整，简单做法是从最后一个节点往上调整，但实际上只要对有孩子的节点从下往上调整即可
        for (int i = heap.length/2 - 1; i >= 0; i--) {
            adjust(i);
        }
     }
     private void adjust(int i) {
        // 找到左右孩子的下标
        int right = (i + 1) * 2;
        int left = right - 1;
        // 找到父节点和左右孩子三个节点中最小的那一个
        if (left < heap.length && heap[left] < heap[i]) {
            min = left;
        }
        if (right < heap.length && heap[right] < heap[min]) {
            min = right;
        }
        // 如果最小的节点就是根节点，则调整结束，返回
        if (min == i) {
            return;
        }
        // 较小的节点和父节点交换（小数上浮）
        swap(i, min);
        // 递归调整下一层
        adjust(min);
     }
     private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
     }
}

三、大根堆

面试题 17.14. 最小K个数