一. 题目

1. 模拟堆

2. 堆排序

二. 思路

1. 模拟堆

2. 堆排序

三. 代码

1. 模拟堆

import java.io.*;

public class Main
{
    static final int N = (int) 1e5 + 10;
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String[] rs;

    int n, m;//n个节点, m个操作
    int[] heap = new int[N];
    int[] pk = new int[N], kp = new int[N];//第k个插入的数下标是几，下标为p的数是第几个插入的。

    public static void main(String[] args) throws Exception
    {
        Main main = new Main();
        main.work();
    }

    void swap(int[] a, int x, int y)//x, y为逻辑交换的位置
    {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    void heapSwap(int x, int y)//x,y为实际堆下标
    {
        swap(pk, kp[x], kp[y]);//交换pk
        swap(kp, x, y);//交换kp
        swap(heap, x, y);//交换堆值
    }

    void up(int u)
    {//u/2合法才能比较
//        if (u / 2 == 0 || heap[u / 2] <= heap[u]) return;
//        heapSwap(u, u / 2);
//        up(u / 2);

        while (u / 2 > 0 && heap[u / 2] > heap[u])
        {
            heapSwap(u / 2, u);
            u /= 2;
        }
    }

    void down(int u)
    {
//        int t = u;
//        if (u * 2 <= n && heap[t] > heap[u * 2]) t = u * 2;
//        if (u * 2 + 1 <= n && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;
//        if (u == t) return;
//        heapSwap(u, t);
//        down(t);

        while (true)
        {
            int t = u;
            if (u * 2 <= n && heap[t] > heap[u * 2]) t = u * 2;
            if (u * 2 + 1 <= n && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;

            if (u == t) break;
            heapSwap(u, t);
            u = t;
        }
    }

    void work() throws Exception
    {
        rs = br.readLine().split(" ");
        m = Integer.parseInt(rs[0]);

        int t = 0;//插入时间
        StringBuilder ans = new StringBuilder();
        while (m-- > 0)
        {
            rs = br.readLine().split(" ");
            if ("I".equals(rs[0]))
            {
                int x = Integer.parseInt(rs[1]);
                heap[++n] = x;
                pk[++t] = n;
                kp[n] = t;
                up(n);
            } else if ("PM".equals(rs[0])) ans.append(heap[1]).append("\n");
            else if ("DM".equals(rs[0]))
            {
                heapSwap(1, n--);
                down(1);
            } else if ("D".equals(rs[0]))
            {
                int p = pk[Integer.parseInt(rs[1])];
                heapSwap(p, n--);
                up(p);
                down(p);
            } else if ("C".equals(rs[0]))
            {

                int p = pk[Integer.parseInt(rs[1])], x = Integer.parseInt(rs[2]);
                heap[p] = x;
                up(p);
                down(p);
            }
        }

        bw.write(ans.toString());
        bw.close();
    }
}

2. 堆排序

import java.io.*;

public class Main
{
    static final int N = (int) 1e5 + 10;
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String[] rs;

    int n, m;//n个节点, m个操作
    int[] heap = new int[N];

    public static void main(String[] args) throws Exception
    {
        Main main = new Main();
        main.work();
    }

    void swap(int x, int y)//x, y为逻辑交换的位置
    {
        int temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }

    void down(int u)
    {
//        int t = u;
//        if (u * 2 <= n && heap[t] > heap[u * 2]) t = u * 2;
//        if (u * 2 + 1 <= n && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;
//        if (u == t) return;
//        heapSwap(u, t);
//        down(t);

        while (true)
        {
            int t = u;
            if (u * 2 <= n && heap[t] > heap[u * 2]) t = u * 2;
            if (u * 2 + 1 <= n && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;

            if (u == t) break;
            swap(u, t);
            u = t;
        }
    }

    void work() throws Exception
    {
        rs = br.readLine().split(" ");
        n = Integer.parseInt(rs[0]);
        m = Integer.parseInt(rs[1]);

        rs = br.readLine().split(" ");
        for (int i = 1; i <= n; ++i)
            heap[i] = Integer.parseInt(rs[i - 1]);

        /*
            若每次一个一个加入到堆
            是nlogn建堆

            若从n/2逐层上down，则是on建堆
         */
        for (int i = n / 2; i > 0; --i)
            down(i);
        StringBuilder ans = new StringBuilder();
        while (m-- > 0)
        {
            ans.append(heap[1]).append(" ");
            heap[1] = heap[n--];
            down(1);
        }

        bw.write(ans.toString());
        bw.close();
    }
}