学步园

本章主要介绍“堆”和“优先队列”数据结构的使用。

堆可分为大根堆和小根堆。堆是某个节点的值总是不大于（大根堆）或不小于（小根堆）其父节点的完全树。常见的堆有二叉堆和斐波那契堆，本章讲的是二叉堆。

由于二叉堆是完全二叉树，所以我们在建堆的时候可以考虑用C++中的vector来作为存储结构。

堆有两个比较重要的操作：插入和删除。插入时，我们一般将新插入的元素放在末尾，这时需要做向上调整；删除时一般是删除“根”节点元素，这时需要做向下调整，以确保堆的性质。

所谓优先队列是不同于先进先出的普通队列，而是每次从队列中取出具有最高优先权的元素。根据优先队列这一特点（每次取出最高优先权的元素），我们可以很自然地想到用堆来实现优先队列。补充一句：优先队列是一个非常有用的数据结构，在实际的编程中常常用到，在C++中有模板库，可以直接调用。

具体实现见代码：

#include<stdio.h>
#include<vector>
#include<stdexcept>
using namespace std;

//堆数据结构的实现（小根堆）
template <typename T>
class Heap
{

public:
	Heap()
	{
	}

	Heap(T elements[], int arraySize)
	{
		for(int i=0; i<arraySize; i++){
			add(elements[i]);
		}
	}

	void add(T element)
	{
		int currentIndex;
		v.push_back(element);
		currentIndex = v.size()-1;
		while(currentIndex > 0){
			int parentIndex = (currentIndex - 1) / 2;
			if(v[parentIndex] > v[currentIndex]){
				T temp = v[parentIndex];
				v[parentIndex] = v[currentIndex];
				v[currentIndex] = temp;
			}
			else{
				break;
			}
			currentIndex = parentIndex;
		}
	}

	T remove() throw(runtime_error)
	{
		if(v.size() == 0){
			throw runtime_error("Heap is empty");
		}

		T removedElement = v[0];
		v[0] = v[v.size()-1];
		v.pop_back();

		int currentIndex = 0;
		while(currentIndex < v.size()){
			int leftChildIndex = 2 * currentIndex + 1;
			int rightChildIndex = 2 * currentIndex + 2;
			
			if(leftChildIndex >= v.size())
				break;
			int minIndex = leftChildIndex;
			if(rightChildIndex < v.size()){
				if(v[minIndex] > v[rightChildIndex]){
					minIndex = rightChildIndex;
				}
			}
			if(v[currentIndex] > v[minIndex]){
				T temp = v[currentIndex];
				v[currentIndex] = v[minIndex];
				v[minIndex] = temp;
				currentIndex = minIndex;
			}
			else{
				break;
			}
		}
		return removedElement;
	}

	int getSize(){
		return v.size();
	}

private:
	vector<T> v;
};

//利用堆实现的优先队列（每次弹出最小的元素）
template <typename T>
class PriorityQueue
{
public:
	PriorityQueue()
	{
	}

	void enqueue(T element)
	{
		heap.add(element);
	}

	T dequeue() throw (runtime_error)
	{
		heap.remove();
	}

	int getSize()
	{
		return heap.getSize();
	}

private:
	Heap<T> heap;
};

//堆排序的实现
void heapAdjust(int a[], int s, int m){ //向下调整，建立大根堆
	int temp = a[s];
	int i, j;
	for(j=s*2; j<=m; j*=2){
		if(j<m && a[j]<a[j+1]){
			j++;
		}

		if(temp >= a[j]){
			break;
		}
		a[s] = a[j];
		s = j;
	}
	a[s] = temp;
}

void HeapSort(int a[], int n)
{
	int i;

	for(i=(n-1)/2; i>=0; i--){
		heapAdjust(a, i, n-1);
	}
	for(i=n-1; i>0; i--){
		int temp = a[i];
		a[i] = a[0];
		a[0] = temp;
		heapAdjust(a, 0, i-1);
	}
}

int main()
{
	int a[7] = {12, 34, 11, 13, 29, 48, 35};

	HeapSort(a, 7);

	for(int i=0; i<7; i++){
		printf("%d ", a[i]);
	}

	return 0;
}