C++ルートヒープソート
1011 ワード
/// /
void heap_adjust(int *a,int node,const int isize)
{
int leftnode = 2*node;
int rightnode = 2*node+1;
int largest = node;
if(leftnode<=isize && a[leftnode]>a[node])
{
largest = leftnode;
}
if(rightnode<=isize && a[rightnode]>a[largest])
{
largest = rightnode;
}
if(largest!=node)
{
swap(a[node],a[largest]);
heap_adjust(a,largest,isize);
}
}
void bulid_max_heap(int *a,int isize)
{
for (int i=isize/2;i>0;--i)
{
heap_adjust(a,i,isize);
}
}
void heap_sort(int *a,int isize)
{
for(int i=isize;i>0;i--)
{
swap(a[1],a[i]); // ,
heap_adjust(a,1,i-1); //
}
}
int main()
{
int a[] = {7,1,2,123,23,45,2135,5};
bulid_max_heap(a,a[0]);
for (int i=1;i<8;i++)
{
printf("%d
",a[i]);
}
printf("
");
heap_sort(a,a[0]);
for (int i=7;i>0;i--)
{
printf("%d
",a[i]);
}
system("pause");
return 0;
}