堆排序

发布时间:2019年09月15日 阅读:223 次

堆排序 -- 注意headsort中 m的使用
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int h[80000000];
int m;
void siftdown(int i){
   int f = 0;
   while(i*2<=m){
      int t;
      if(h[i]<h[i*2])t = i;
      else t = i*2;
      if((i*2+1)<=m&&h[i*2+1]<h[t])t = i*2+1;
      //边界
      if(t==i){
        //f =1 ;
        break;
      }
      else{
          swap(h[i],h[t]);
          i = t; //交换
        }
   }
}
void heapsort(){
    int u = m;
   while(m>1){
     swap(h[1],h[m]);
     m--;
     siftdown(1);//向下调整
   }
}
int main()
{
    int n;
    cin>>n>>m;
    int yy= m;
    for(int i=1;i<=m;i++){
        scanf("%d",&h[i]);
    }
    for(int i=m/2;i>=1;i--){
        siftdown(i);
    }
    for(int i=1;i<=n-m;i++){
        int num;
        scanf("%d",&num);
//        cout<<" "<<num<<" "<<endl;
        if(num<h[1]);
        else{

            h[1] = num;
            for(int j=m/2;j>=1;j--){
                siftdown(j);
            }
        }
    }

    int top = 1;
    heapsort();
    for(int i=1;i<=yy;i++){
        if(top)top = 0;
        else printf(" ");
        printf("%d",h[i]);
    }
    printf("\n");

    return 0;
}
/*
10 8
1 2 4 3  6 5 8 7 10 9
*/


Tag:
相关文章

发表评论: