Acwing.838.堆排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了Acwing.838.堆排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基础堆操作

题目

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式

第一行包含整数n和m。
第二行包含n个整数，表示整数数列。

输出格式

共—行，包含m个整数，表示整数数列中前m小的数。

数据范围

1 ≤m ≤n ≤10^ 5，1≤数列中元素≤10^9

输入样例:

5 3
4 5 1 3 2

输出样例:

1 2 3

题解

import java.util.Scanner;

/**
 * @author akuya
 * @create 2023-06-28-14:15
 */
public class heap {
    static int N=100010;
    static int n,m,size=0;
    static int h[]=new int[N];
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        size=n;
        for(int i=1;i<=n;i++)h[i]=scanner.nextInt();
        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);
        }

    }
    public static void down(int u){
        int t=u;
        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(u!=t){
            swap(h,u,t);
            down(t);
        }
    }

    public static void up(int u){
        while(u/2!=0&&h[u/2]>h[u]){
            swap(h,u/2,u);
            u/=2;
        }
    }


    public static void swap(int arr[],int x,int y){
        arr[x]=arr[x]^arr[y];
        arr[y]=arr[x]^arr[y];
        arr[x]=arr[x]^arr[y];
    }


}

进阶模拟堆

题目

维护一个集合，初始时集合为空，支持如下几种操作:
1."l ×”，插入一个数x;
2."PM”，输出当前集合中的最小值;
3.“DM”，删除当前集合中的最小值(当最小值不唯一时，删除最早插入的最小值);
4."D k”，删除第k个插入的数;
5."C k x”，修改第k个插入的数，将其变为x;
公
现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。

输入格式

第一行包含整数N。
接下来N行，每行包含一个操作指令，操作指令为"l x”，“PM”，“DM”，"D k"或"C k x"中的一种。

输出格式

对于每个输出指令"PM”，输出一个结果，表示当前集合中的最小值。每个结果占一行。

数据范围

1≤N≤105-109<a ≤ 109数据保证合法。

输入样例:

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例:

-10
6

题解

 import java.util.Scanner;

/**
 * @author akuya
 * @create 2023-06-28-14:15
 */
public class heap {
    static int N=100010;
    static int n,m,size=0;
    static int h[]=new int[N];
    static int ph[]=new int[N];
    static int hp[]=new int[N];

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m=0;
        while(n--!=0){
            String op=scanner.next();
            int k,x;
            if(op.equals("I")){
                x=scanner.nextInt();
                size++;//记录下标
                m++;//记录第几个插入的数
                ph[m]=size;
                hp[size]=m;
                h[size]=x;
                up(size);

            }else if(op.equals("PM")) System.out.println(h[1]);
            else if(op.equals("DM")){
                heap_swap(h,1,size);
                size--;
                down(1);
            }else if(op.equals("D")){
                k=scanner.nextInt();
                k=ph[k];
                heap_swap(h,k,size);
                size--;
                down(k);
                up(k);
            }else{
                k=scanner.nextInt();
                x=scanner.nextInt();
                k=ph[k];
                h[k]=x;
                down(k);
                up(k);
            }

        }

    }
    public static void down(int u){
        int t=u;
        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(u!=t){
            heap_swap(h,u,t);
            down(t);
        }
    }

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


    public static void swap(int arr[],int x,int y){
        arr[x]=arr[x]^arr[y];
        arr[y]=arr[x]^arr[y];
        arr[x]=arr[x]^arr[y];
    }

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

    }



}

思路

将基础堆排序模板中三个方法修改为如下方法，即可实现进阶堆排序，多了两个数组ph，hp。
ph[k]:第K个插入的点在堆中的下标是什么。
hp[k]:下标为K的点事第几个插入的。
通过ph与hp即可实现进阶题目的后两个操作。文章来源地址https://www.toymoban.com/news/detail-520924.html

到了这里，关于Acwing.838.堆排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！