求n个数中前m个大的数的堆排序版本

小咪咪 2022-04-17 06:13 176阅读 0赞

堆排序就是先求出最大的数，然后求出次大的数，然后求出第三大的数，依次类推，而这个题只要求求出前m个大的数，所以用堆排序应该是效率比较高的。

heapsort()
    {
           build_max_heap(int n);   //建立最大堆
           for (i=n;i>=2;i--)
           {
                     exchange(a[1],a[i]);   // 交换第一个数和堆中的最后一个数，此时最大的数就成堆的最后一个数
                      heapsize--;
                      max_heapify(1);   //保持最大堆
           }
    }

具体代码：

#include<stdio.h>
    #define MAXLENGTH 1000002
    int a[MAXLENGTH];
    int heapsize;
    int m;
    
    void exchange(int &a,int &b)
    {
        int t;
        t=a;
        a=b;
        b=t;
    }
    int parent(int i)
    {
        return i>>1;
    }
    
    int left(int i)
    {
        return i<<1;
    }
    
    int rigth(int i)
    {
        return (i<<1)+1;
    }
    
    void max_heapify(int i)
    {
        int l=left(i);
        int r=rigth(i);
        int largest;
        if (l<=heapsize && a[l]>a[i])
            largest = l;
        else
            largest = i;
        if (r<=heapsize && a[r]>a[largest])
            largest = r;
        if (largest!=i)
        {
            exchange(a[i],a[largest]);
            max_heapify(largest);
        }
    }
    
    void build_max_heap(int n)
    {
        int i;
        heapsize=n;
        for (i=n/2;i>=1;i--)
            max_heapify(i);
    }
    
    void heapsort(int n)
    {
        int i;
        build_max_heap(n);
        printf("%d",a[1]);
        m--;
        for (i=n;i>=1;i--)
        {    
            if (m==0)
                break;
            printf(" ");
            exchange(a[1],a[i]);
            heapsize--;
            max_heapify(1);
            printf("%d",a[1]);
            m--;
        }
    }
    
    
    int main()
    {
        int i,n;
        while(scanf("%d %d",&n,&m)!=EOF)
        {
            for (i=1;i<=n;i++)
                scanf("%d",a+i);
            heapsort(n);
            printf("\n");
        }
        //for (i=1;i<=n;i++)
            //printf("%d ",a[i]);
        return 0;
    }