2、堆排序&数组模拟堆排序&模拟堆

AcWing 838. 堆排序

AcWing 83. 模拟堆（模板）

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.duipaixu();
    }
    int N=100010;
    int h[]=new int[N];
    int size=0;
    void down(int u){
        int min=u;
        //size是实时变化的，反映堆的长度
        if(u*2<=size&&h[min]>h[u*2]) min=u*2;
        if(u*2+1<=size&&h[min]>h[u*2+1]) min=u*2+1;
        if(min!=u){
            int temp=h[u];
            h[u]=h[min];
            h[min]=temp;
            //交换完毕
            down(min);
        }
    }
    void duipaixu(){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        for (int i = 1; i <= n; i++) h[i]=sc.nextInt();
        size=n;
        for(int i=n/2;i>0;i--) down(i);
        while(m-->0){
            System.out.print(h[1]+" ");
            h[1]=h[size];
            size--;
            down(1);
        }
    }
}

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.monidui();
    }

    int N = 100010;
    int h[] = new int[N];
    int hp[] = new int[N];
    int ph[] = new int[N];
    int size;

    public static void swap(int arr[], int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    void heap_swap(int a, int b) {
        swap(ph, hp[a], hp[b]);
        swap(hp, a, b);
        swap(h, a, b);
    }

    void down(int u) {
        int min = u;
        //size是实时变化的，反映堆的长度
        if (u * 2 <= size && h[min] > h[u * 2]) min = u * 2;
        if (u * 2 + 1 <= size && h[min] > h[u * 2 + 1]) min = u * 2 + 1;
        if (min != u) {
            heap_swap(u,min);
            //交换完毕
            down(min);
        }
    }

    void up(int u) {
        while (u / 2 != 0 && h[u] < h[u / 2]) {
            heap_swap(u, u / 2);
            u >>= 1;
        }
    }

    void monidui() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = 0;
        while (n-- > 0) {
            String op = sc.next();
            if (op.equals("I")) {
                int x = sc.nextInt();
                size++;
                m++;
                ph[m] = size;
                hp[size] = m;
                h[size] = x;
                up(size);
            }
            if (op.equals("PM")) {
                System.out.println(h[1]);
            }
            if (op.equals("DM")) {
                heap_swap(1, size);
                size--;
                down(1);
            }
            if (op.equals("D")) {
                int k = sc.nextInt();
                k = ph[k];
                heap_swap(k, size);
                size--;
                up(k);
                down(k);
            }
            if (op.equals("C")) {
                int k = sc.nextInt();
                int x = sc.nextInt();
                k = ph[k];
                h[k] = x;
                up(k);
                down(k);
            }
        }
    }
}