heapsort.cpp

堆排序的算法,原书带的并不能直接使用,这是本人改的直接可用的

struct elemType{
int key;
} He[20000];

typedef struct{
  elemType *r;
  int length;
  int listsize;
}Sqlist;
typedef Sqlist HeapType;

void HeapAdjust(HeapType &H,int s, int m){
elemType rc;
int j;
	rc=H.r[s];
for(j=2*s;j<=m;j*=2){
  if(j<m&&(H.r[j].key>H.r[j+1].key)) ++j;
  if(!(rc.key>H.r[j].key)) break;
  H.r[s]=H.r[j];
  s=j;
}
H.r[s]=rc;
}

void HeapSort(HeapType &H){
	int i;
	
   elemType t;
	for(i=(H.length/2);i>0;--i)
		HeapAdjust(H,i,H.length);
	for(i=H.length;i>1;--i){
	    t=H.r[1];
		H.r[1]=H.r[i];
		H.r[i]=t;
		
		HeapAdjust(H,1,i-1);
	}
}

int min(HeapType &kk)  //确定最小元素并删除
{
int j;
j=kk.r[kk.length].key;
kk.r[kk.length].key=-1;
kk.length=kk.length-1;

HeapSort(kk);

return j;
}

void insert(int x,HeapType kk)//将x坐标插入到kk并维持全序，确定x坐标是否是kk的一个成员
{
kk.length=kk.length+1;
kk.r[kk.length].key=x;
HeapSort(kk);
}
#include <iostream>
#include <stdlib.h>
#include <math.h>
void main()
{ int i,m;

HeapType He;
He.length=0;

He.r=(elemType*)malloc(30000*sizeof(elemType));

for (i=1;i<=3;i++){
	std::cin>>He.r[i].key;
	He.length=He.length+1;
   }
HeapSort(He);
for (i=1;i<=3;i++){
	std::cout<<He.r[i].key<<std::endl;
}
min(He);
for (i=1;i<=3;i++){
	std::cout<<He.r[i].key<<std::endl;
}
std::cin>>m;
insert(m,He);
for (i=1;i<=4;i++){
	std::cout<<He.r[i].key<<std::endl;
}
}