堆排序

2021-09-11

堆分为小根堆和大根堆（本质上是一颗完全二叉树）

堆可以干什么？

找到一个集合当中的最小值
删除一个集合当中的最小值
插入一个数

如何调整小根堆或者大根堆？

以小根堆为例子

down -> 选择这个数和子节点的最小值进行交换
up -> 选择这个节点与父节点进行交换

如何存储堆？

下标从 1 开始保证了数组子节点的可行性

选择用数组的形式来存储 1 2 3 4 5 6 7 8
k 的子节点为 2k 2k+1

如何手写一个堆

插入一个数：heap[++size] = x;
求集合当中的最小元素：heap[1];
删除最小的元素：heap[1] = heap[size]; size ++; down(1) //将末尾的元素覆盖到头节点，数组删除头节点是很麻烦的一件事
删除任意一个元素：heap[k] = heap[size]; size ++; down(k); up(k)；
修改任意一个元素：heap[k] = x;up(x);down(x); 保证 down 和 up 只执行一次

模版题

838. 堆排序

import java.util.*;
import java.io.*;
public class Main{
    public static int size = 0;
    public static int h[];
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        size = n;
        h = new int[n + 1];
        for(int i = 1 ; i <= n ; i ++){
            h[i] = in.nextInt();
        }

        //初始化小根堆 优化时间复杂度：nlogn -> n
        for(int i = n/2 ; i != 0 ; i --){
            down(i);
        }

        while(m -- != 0){
            log.write(h[1] + " ");
            //删除最小值
            h[1] = h[size];
            size --;
            down(1);
        }
        log.flush();
        log.close();
        in.close();
    }
    //向下调整小根堆
    public static void down(int u){
        int t = u; //用t来存储最小值的编号
        if(u*2 <= size && h[u*2] < h[t]) t = u * 2;
        if(u*2+1 <= size && h[u*2+1] < h[t]) t = u * 2 + 1;
        if(t != u){
            int c = h[t];
            h[t] = h[u];
            h[u] = c;
            down(t); //递归调整最小值
        }
    }
    //向上调整小根堆
    public static void up(int u){
        while(u/2 != 0 && h[u] < h[u / 2]){
            int c = h[u];
            h[u] = h[u/2];
            h[u/2] = c;
            u /= 2;
        }
    }
}

839. 模拟堆

import java.util.*;
import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] h;
    static int[] ph;  //存放第k个插入点的下标
    static int[] hp;  //存放堆中点的插入次序
    static int size;
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        h = new int[n + 1];
        ph = new int[n + 1];
        hp = new int[n + 1];
        size = 0;
        int m=0;      //m用来记录插入的数的个数
        while(n-- > 0){
            String[] s = read.readLine().split(" ");
            String op = s[0];
            if("I".equals(op)){
                int x = Integer.valueOf(s[1]);
                m++;
                h[++size]=x;
                ph[m]=size;
                hp[size]=m;
                //down(size);
                up(size);
            }else if("PM".equals(op))    log.write(h[1] + "\n");
            else if("DM".equals(op)){
                heapSwap(1,size);
                size--;
                down(1);
            }else if("D".equals(op)){
                int k = Integer.valueOf(s[1]);
                int u=ph[k];                //这里一定要用u=ph[k]保存第k个插入点的下标
                heapSwap(u,size);          //因为在此处heapSwap操作后ph[k]的值已经发生
                size--;                    //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
                up(u);
                down(u);
            }else if("C".equals(op)){
                int k = Integer.valueOf(s[1]);
                int x = Integer.valueOf(s[2]);
                h[ph[k]]=x;                 //此处由于未涉及heapSwap操作且下面的up、down操作只会发生一个所以
                down(ph[k]);                //所以可直接传入ph[k]作为参数
                up(ph[k]);
            }
        }
        log.flush();
    }

    //这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
    //之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
    //从而我们需要对应到原先第K个堆中元素
    //如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
    //h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
    public static void heapSwap(int u, int v){
        swap(h,u,v);
        swap(hp, u, v);
        swap(ph, hp[u], hp[v]);
    }

    public static void swap(int[] a, int u, int v){
        int tmp = a[u];
        a[u] = a[v];
        a[v] = tmp;
    }

    public static void down(int u){
        int t = u;
        if(u * 2 <= size && h[t] > h[u * 2]) t = u * 2;
        if(u * 2 + 1 <= size && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
        if(u != t){
            heapSwap(u, t);
            down(t);
        }
    }

    public static void up(int u){
        if(u / 2 > 0 && h[u] < h[u / 2]){
            heapSwap(u, u / 2);
            up(u/2);
        }
    }
}