heap_sort（）这个函数不知道有什么问题，堆的性质维护和建堆的函数都调试过了，没问题
以下是部分代码，红色部分请大家重点为我看看
//---------------------------------------------------------------------------
//最大堆类的声明
#ifndef MaxheapH
#define MaxheapH
#include"array.h"
class max_heap{
private:
array data;//数据数组
size_t heap_size;//堆的大小
size_t parent(long i);//返回第i个元素的父亲
size_t left(long i);//返回第i个元素的左孩子
size_t right(long i);//返回第i个元素的右孩子
public:
void heapify(int i);//堆的性质维护
max_heap(){};//缺省的构造函数
max_heap(array &a);//用数组a创建一个最大堆
int maximum();//返回最大值
int extract_max();//返回最大值且从堆中删除
void increase_key(int i,int key);//将第i个元素的键值增加为key
void insert(int key);//将键值key插入到堆中
void swap(size_t i,size_t j);//交换data[i]，data[j]
void reduce();//对规模缩小1
};
//---------------------------------------------------------------------------
#endif
#include"maxheap.h"
size_t max_heap::parent(long i)//计算节点i的父节点下标
{ if(i%2)
return i/2;
else
return i/2+1;
}
size_t max_heap::left(long i){//计算节点i的左孩子节点下标
return 2*i+1;
}
size_t max_heap::right(long i){//计算节点i的右孩子节点下标
return 2*(i+1);
}
int max_heap::maximum(){//返回堆中最大元素值
return this->data[0];
}
int max_heap::extract_max(){//返回堆中最大元素值并将其在堆中删除
int max=-1;
if(this->heap_size>=1){
max=this->data[0];
this->data[0]=this->data[this->heap_size-1];
this->heap_size--;
this->heapify(0);
}
return max;
}
void max_heap::increase_key(int i,int key){//将节点i的值改变为key
if(key>this->data[i]){
this->data[i]=key;
while(i>0&&this->data[this->parent(i)]<this->data[i]){
this->swap(i/2,i);
i/=2;
}
}
}
void max_heap::insert(int key){//将值为key的节点插入到堆中
this->data[(this->heap_size)++]=-numeric_limits<int>::max();
increase_key(this->heap_size,key);
}
void max_heap::swap(size_t i,size_t j){//交换堆中两个节点的值
int temp;
temp=this->data[i];
this->data[i]=this->data[j];
this->data[j]=temp;
}
void max_heap::reduce(){//减少堆的大小
this->heap_size--;
}
void max_heap::heapify(int i){//对性质的维护
int l,r,largest;
l=this->left(i);
r=this->right(i);
if((l<=this->heap_size)&&(this->data[i]<this->data[l]))
largest=l;
else
largest=i;
if((r<=this->heap_size)&&(this->data[r]>this->data[largest]))
largest=r;
if(largest!=i){
this->swap(largest,i);
this->heapify(largest);
}
}
max_heap::max_heap(array &a){//创建堆
int i;
this->data=a;
size_t n=this->heap_size=a.size();
for(i=n/2-1;i>=0;i--)
this->heapify(i);
//for(i=0;i<n;i++)
// cout<<this->data[i]<<",";
//cout<<endl;
}
void heap_sort(array& a){
max_heap b(a);
int i,n=a.size();
for(i=n-1;i>=0;i--){
a[i]=b.maximum();//将堆b中的最大元素拷贝到a[i]
if(i>0){
b.swap(0,i);//将堆b中的根与最后一片叶子交换
b.reduce();//将堆b缩小
b.heapify(0);//对b维护堆性质
}
}
}
void main(){
array a;
fill_array(a,1000,10);//填充一个具有10个元素的数组
cout<<"排序前："<<a<<endl;//输出排序前的数组
heap_sort(a);//排序
cout<<"排序后："<<a<<endl;//输出排序后的数组
//max_heap b(a);
}
程序代码：
