2016新编堆的遍历与堆排序.doc

/*最大堆问题,堆数据结构是一颗完全二叉树,用数组来完成其物理实现,逻辑上实际是一种树形结构,
r是下标,parent(r)=int((r-1)/2);
leftchild(r)=2r+1;
rightchild(r)=2r+2;*/

template<class Elem>
class maxheap
{
private:
Elem* heapArray;
int maxsize;
int n;//堆的大小
public:
maxheap(int size = 10){
maxsize = size;
heapArray = new Elem[maxsize];//注意为中括号
n = 0;
}
~maxheap() {delete [] heapArray;}
int heapsize() {return n;}
int parent(int pos) {
return (pos-1)/2;
}
int leftchild(int pos) {
return 2*pos+1;
}
int rightchild(int pos) {
return 2*pos+2;
}
bool insert(Elem& e);
bool remove(int pos);
bool creatHeap(int ArrLen,Elem* arr);
void preorder(int pos);
void heapSort(int arrlen);
void print();
};
template<class Elem>
bool maxheap<Elem>::insert(Elem& e)
{
if(n>=maxsize-1)return false;
heapArray[n] = e;
// cout<<heapArray[n];
int temp = n;
Elem ha;
while(parent(temp)>=0 && heapArray[parent(temp)]<heapArray[temp]){
ha = heapArray[parent(temp)];
heapArray[parent(temp)] = heapArray[temp];
heapArray[temp] = ha;
// cout<<heapArray[temp]<<heapArray[parent(temp)];
temp = parent(temp);
}
n +=1;
return true;
}
template<class Elem>
bool maxheap<Elem>::creatHeap(int ArrLen, Elem* arr)
{
int n = ArrLen;
// heapArray = new Elem[ArrLen];
for(int i = 0; i<ArrLen-1 && arr[i]; i++){
insert(arr[i]);
}
return true;
}
template<class Elem>
bool maxheap<Elem>::remove(int pos)
{
if(pos<0 || pos>n)return false;
Elem temp;
temp = heapArray[pos];
heapArray[pos] = heapArray[n-1];
heapArray[n-1] = temp;
n = n-1;//删除一个节点后,堆节点数减1
int j = leftchild(pos);
while(j<=n-1){

if( heapArray[leftchild(pos)] < heapArray[rightchild(pos)] && rightchild(pos) <= n-1 ) j = rightchild(pos);//此时,j指向孩子中较大节点
if( heapArray[pos] >= heapArray[j] )break;//如果父节点比左右节点中较大节点大,则循环退出
temp = heapArray[j]; //父节点与较大节点交换
heapArray[j] = heapArray[pos];
heapArray[pos] = temp;
pos = j;
j = leftchild(pos);
}
return true;
}
templat