堆排序

应用场景：动态维护最小值或最大值

含义

一棵完全二叉树
大根堆：根元素大于等于左右子树的所有值
小根堆：根元素小于等于左右子树的所有值

存储方式

用一个数组就可以存储，从下标为1的位置开始，再用一个值 size 存储当前堆的大小。
假设指向根节点的下标为x，它的左子树根节点下标为 2 * x ，它的右子树下标为 2 * x + 1

操作

//向上
void up(int x) {
    //向上递归将x与父节点交换（如果需要交换的话）
}
//向下
void down(int x) {
    //向下递归将x与左右子节点交换（如果需要的话）
}

问题

各种操作的方法：

//1. 插入一个数
heap[++size] = x;
up(size);
//2. 求集合中的最小值
heap[1];
//3. 删除最小值
swap(heap, 1, size);
size--;
down(1);
//4. 删除任意元素
swap(heap, k, size);
size--;
down(k);
up(k);
//修改任意元素
heap[k] = x;
down(k);
up(k);

堆初始化的时间复杂度？
自下而上：O(n)
自上而下：O(nlogn)

例题

838. 堆排序

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

// 大根堆实现，不过本题要用小根堆，无所谓了，不针对该题
import java.util.*;
public class Main {
    static int n, m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Heap heap = new Heap(n);
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        heap.init(a);
        for (int i = 0; i < m; i++) {
            System.out.print(heap.pop() + " ");
        }
    }
}
class Heap {
    int n, size;
    int[] a;
    Heap(int n) {
        this.n = n + 1;
        a = new int[n + 1];
    }
    void init(int[] b) {
        size = b.length;
        for (int i = 1; i <= size; i++) {
            a[i] = b[i - 1];
        }
        // 自下而上初始化 o(n)
        for (int i = size / 2; i > 0; i--) {
            down(i);
        }
        // 自上而下初始化 O(nlogn)
        // for (int i = 1; i <= size; i++) {
        //     up(i);
        // }
    }
    int pop() {
        int res = a[1];
        a[1] = a[size];
        size--;
        return res;
    }
    void down(int idx) {
        int left = idx * 2, right = idx * 2 + 1;
        if (idx <= size) {
            int maxIdx = idx;
            if (left <= size && a[left] > a[maxIdx]) maxIdx = left;
            if (right <= size && a[right] > a[maxIdx]) maxIdx = right;
            if (maxIdx != idx) {
                swap(idx, maxIdx);
                down(maxIdx);
            }
        }
    }
    void up(int idx) {
        if (idx / 2 > 0 && a[idx] > a[idx / 2]) {
            swap(idx, idx / 2);
            up(idx / 2);
        }
    }
    void swap(int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}