学步园

原理：堆排序是基于二叉树实现的，主要步骤为：

先建立二叉堆(堆元素从 n/2 - -  1 执行向上调整操作) (二叉堆分为小根堆与大根堆)，再不断执行以下步骤：将根元素与根底元素互换，且将未排序的堆总元素减一，并执行将根顶元素向下调整操作，直到未排序堆总元素为0

具体代码如下：

//////////////////////////////////
// 实现小根堆的相关操作
/////////////////////////////////
bool isLess(int a, int b) { 
	return a<b; 
}

void exch(int &a, int &b) { 
	int temp=a;
	a=b;
	b=temp;
}

//向上调整函数
void shiftup(int *data, int pos){
	while(pos/2>=1)       //pos/2>=1要注意
	{
		if(isLess(data[pos/2], data[pos])) 
			break;
		exch(data[pos/2], data[pos]);
		pos=pos/2;
	}
}
//向下调整函数
void shiftdown(int *data, int pos, int n){
	while(2*pos<=n){		//data[0]代表数组的元素个数，2*pos<=n细节要注意
		int k=2*pos;
		if(k<n && isLess(data[k+1], data[k])) k++;  //k<n要注意
		if(isLess(data[pos], data[k])) break;
		exch(data[pos], data[k]);
		pos=k;
	}
}

//堆排序(降序排序)
void heap_sort(int *data){
	int i=0;
	for(i=data[0]/2; i>=1; i--)
		shiftup(data, i);
	int n = data[0];
	while(n>=1){	//n>=1要注意
		exch(data[1], data[n]);
		shiftdown(data, 1, --n);  //--n要注意	
	}
}

优先队列的实现原理是利用了二叉堆的性质，一般至少包括2个操作:

插入元素：insert(先判断插入后元素的个数（n+1）是否超过优先队列的最大个数，在将data[++n]=val,并将该元素进行向上调整操作)

返回队列的最小值(或最大值): extractmin(首先判断优先队列中是否有元素(n-1<0)，再保存优先队列的首元素，将最后一个元素与第一个元素交换，并将元素个数减一，最后对优先队列首元素执行向下调整操作)

具体代码：

///////////////////////////////////
// 实现优先队列的相关操作
///////////////////////////////////

class prior_queue{
public:
	prior_queue(int m);		//构造函数
	void insert(int val);	//插入元素
	int extractmin();		//取优先队列的最小值
	~prior_queue();			//析构函数
private:
	int *m_data;
	int maxsize;
	int n;
	
private:
	void shiftdown(int pos);	//向下调整
	void shiftup(int pos);		//向上调整
	void exch(int &a, int &b) { int temp=a; a=b; b=temp; }
};

prior_queue::prior_queue(int m){
	m_data = new int[m+1];
	maxsize=m;
	n=0;
}

prior_queue::~prior_queue(){
	delete[] m_data;
}

void prior_queue::shiftdown(int pos){
	while(2*pos<=n){
		int k=2*pos;
		if(k<n && m_data[k+1]<m_data[k]) k++;
		if(m_data[pos]<m_data[k]) break;
		exch(m_data[pos], m_data[k]);
		pos=k;
	}
}

void prior_queue::shiftup(int pos){
	while(pos/2>=1){
		if(m_data[pos/2]<m_data[pos]) break;
		exch(m_data[pos], m_data[pos/2]);
		pos=pos/2;
	}
}

void prior_queue::insert(int val){
	n = n+1;
	if(n>maxsize)	return ;
	m_data[n]=val;
	shiftup(n);
}

int prior_queue::extractmin(){
	if(n-1<0)	return 0;
	int min=m_data[1];
	exch(m_data[1], m_data[n--]);
	shiftdown(1);
	return min;	
}

实现原理：建立一个k个元素的小根堆，来输出数组中的最大的k和元素(或者大根堆，来输出数组中的最小的k的元素)

先对已知数组前k个元素建立一个k小根堆，再将数组的元素(下标从k+1 - -  n)与小根堆根顶元素比较，大则交换，并执行向下调整操作，直至遍历完数组中的全部元素

具体代码：

void top_max_k(int *data, int k){
	int i=0;
	for(i=k/2; i>=1; i--)
		shiftup(data, i);
	i=k+1;
	while(i<=data[0]){
		if(data[i]>data[1]){
			exch(data[i], data[1]);
			shiftdown(data, 1, k);   //shitdown见堆排序中的shiftdown函数
		}
		i++;
	}
}