...85、61、43、45、49),采用堆排序算法完成以下操作

发布网友 发布时间：2022-04-30 09:35

我来回答

共1个回答

热心网友 时间：2022-05-22 02:45

这是我写的C++代码的简单实现

#include<iostream>

using namespace std;

int parent(int i);

int left_child(int i);

int right_child(int i);

void max_heapify(int a[],int i,int heap_size);

void build_max_heap(int a[],int heap_size);

void heap_sort(int a[],int heap_size);

int main()

{

int a[]={51,85,61,43,45,49};

int i;

for(i=0;i<=5;i++){

cout<<" ";cout<<a[i];cout<<" ";}

cout<<endl;

heap_sort(a,5);

for(i=0;i<=5;i++){

cout<<" ";cout<<a[i];cout<<" ";}

cout<<endl;

}

int parent(int i){

return i/2;

}

int left_child(int i){

return 2*i;

}

int right_child(int i){

return 2*i+1;

}

void max_heapify(int a[],int i,int heap_size){

int largest;

int n;

int l=left_child(i);

int r=right_child(i);

if((l<=heap_size)&&(a[l]>a[i]))

largest=l;

else

largest=i;

if((r<=heap_size)&&(a[r]>a[largest]))

largest=r;

if(largest!=i){

n=a[largest];

a[largest]=a[i];

a[i]=n;

max_heapify(a,largest,heap_size);

}}

void build_max_heap(int a[],int heap_size){

        int i;

for(i=heap_size/2;i>=0;i--)

max_heapify(a,i,heap_size);

}

void heap_sort(int a[],int heap_size){

int i,n;

build_max_heap(a,heap_size);

for(i=heap_size;i>=1;i--){

n=a[i];

a[i]=a[0];

a[0]=n;

heap_size--;

max_heapify(a,0,heap_size);

}

}