fork(1) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void sift(int [],int,int);
  5. void BuildMaxHeap(int [],int);
  6. void Heap_sort(int [],int);
  7.  
  8. int main(void){
  9.  
  10.     int heap[13]={50,41,19,81,45,25,56,61,49,10,36,15,90};
  11.     BuildMaxHeap(heap,13);
  12.       cout<<"Heap sort前:";
  13.       for(int i=0;i<13;i++)
  14.       cout<<heap[i]<<" "; 
  15.       cout<<endl;
  16.  
  17.     Heap_sort(heap,13);
  18.  
  19.     cout<<"Heap sort後:";
  20.     for(int i=0;i<13;i++)
  21.      cout<<heap[i]<<" "; 
  22.      cout<<endl;
  23.  
  24.          return 0;  
  25. }
  26.  
  27.  
  28. void BuildMaxHeap(int heap[],int n){
  29.         int i;
  30.         for(i=(n-2)/2;i>=0;i--)
  31.          sift(heap,i,n);
  32.  
  33.      }
  34.  
  35.  
  36. void sift(int a[],int i,int n){
  37.      int temp,j;
  38.      temp=a[i];
  39.      j=2*i+1;
  40.  
  41.      while(j<n){
  42.  
  43.  
  44.  
  45.             if(j+1<n&&a[j]<a[j+1])
  46.             j++;
  47.             if(temp>a[j])
  48.                 break;
  49.  
  50.  
  51.  
  52.  
  53.             a[i]=a[j];    
  54.             i=j;
  55.  
  56.             j=2*i+1;
  57.  
  58.  
  59.      }
  60.      a[i]=temp;
  61.  
  62.      }
  63.  
  64. void Heap_sort(int heap[],int n){
  65.      int k,temp;
  66.  
  67.      while(n>1){
  68.      temp=heap[n-1];
  69.      heap[n-1]=heap[0];
  70.      heap[0]=temp;
  71.      n--;
  72.      k=(n-2)/2;
  73.      for(int i=k;k>=0;k--){
  74.      sift(heap,i,n);}
  75.      }
  76.  
  77.      }
Success #stdin #stdout 0.01s 2680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Heap sort前:90 81 56 61 45 25 50 41 49 10 36 15 19 
Heap sort後:56 61 81 45 25 50 41 49 10 36 15 19 90
https://ideone.com/vVBs8
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!