最近在复习数据结构，从各种数据结构的发明不得感叹人类真的很聪明，创造了各种方式来组织数据，使得人们可以快速的获得某一想要的数据。

二叉堆具有的堆序性质就是如此。

百度百科链接

#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
using namespace std;

#define readint(T) scanf("%d", &T)
const int INF = 0x3f3f3f3f;

template<typename Comparable>
class BHeap
{
	private:
		int currentSize;
		vector<Comparable> array;
		
		void buildHeap();
		void percolateDown(int hole);
		
	public:
		explicit BHeap(int capacity = 100);
		explicit BHeap(const vector<Comparable> &items);
		
		bool isEmpty() const;
		Comparable findMin() const;
		
		void decreaseKey(int p, Comparable delta);
		void increaseKey(int p, Comparable delta);
		
		void insert(const Comparable &x);
		Comparable deleteMin();
		void makeEmpty();
		void print();
};

template<typename Comparable>
void BHeap<Comparable>::insert(const Comparable &x)
{
	if(currentSize == array.size() -1)
		array.resize(array.size()*2);
		
	int hole = ++currentSize;
	
	for(; hole > 1 && x < array[hole/2]; hole /=2)
		array[hole] = array[hole/2];
	array[hole] = x;
}

template<typename Comparable>
Comparable BHeap<Comparable>::deleteMin()
{
	Comparable ERROR = -1;
	if(isEmpty())
	{
		printf("already Empty\n");
		return ERROR;
	}
	
	Comparable minItem = array[1];
	array[1] = array[currentSize--];
	percolateDown(1);
	
	return minItem;
}

template<typename Comparable>
void BHeap<Comparable>::percolateDown(int hole)
{
	int child;
	Comparable tmp = array[hole];
	
	for(; hole*2 <= currentSize; hole = child)
	{
		child = hole*2;
		if(child != currentSize && array[child+1] < array[child])
			child++;
		if(array[child] < tmp)
			array[hole] = array[child];
		else break;
	}
	array[hole] = tmp;
}

template<typename Comparable>
void BHeap<Comparable>::decreaseKey(int p, Comparable delta)
{
	Comparable tmp = array[p]-delta;
	
	if(tmp > array[p])
		printf("The new Key is larger than current Key!!!\n");
	else
	{
		array[p] = tmp;
		int hole;
		for(hole = p; hole > 1 && array[tmp] < array[hole/2]; hole /= 2)
			array[hole] = array[hole/2];
		array[hole] = tmp;
	}
}

template<typename Comparable>
void BHeap<Comparable>::increaseKey(int p, Comparable delta)
{
	Comparable tmp = array[p]+delta;
	
	if(tmp < array[p])
		printf("The new Key is smaller than current Key!!!\n");
	else
	{
		array[p] = tmp;
		percolateDown(p);
	}
}

template<typename Comparable>
BHeap<Comparable>::BHeap(const vector<Comparable> &items):array(items.size()+10), currentSize(items.size())
{
	for(int i = 0; i < items.size(); i++)
		array[i+1] = items[i];
	buildHeap();
}

template<typename Comparable>
void BHeap<Comparable>::buildHeap() //建堆只考虑有子节点的节点
{
	for(int i = currentSize/2; i > 0; i--)
		percolateDown(i);
}

template<typename Comparable>
bool BHeap<Comparable>::isEmpty() const
{
	if(currentSize == 0) return 1;
	return 0;
}

template<typename Comparable>
void BHeap<Comparable>::makeEmpty()
{
	currentSize = 0;
}

template<typename Comparable>
Comparable BHeap<Comparable>::findMin() const
{
	Comparable minItem = array[1];
	return minItem;
}

template<typename Comparable>
void BHeap<Comparable>::print()
{
	for(int i = 1; i <= currentSize; i++) printf(i != currentSize?"%d ":"%d\n", array[i]);
}

int main()
{
	////////////////////////////test
	vector<int> ar;
	
	int minItem, x;
	for(int i = 0; i < 10; i++)
	{
		readint(x);
		ar.push_back(x);
	}
	
	BHeap<int> Heap(ar);
	
	printf("findMin: %d\n", Heap.findMin());
	Heap.print();
	
	printf("Please input a digit:\n");
	readint(x);
	
	printf("after insert a digit\n");
	Heap.insert(x);
	Heap.print();
	
	
	printf("position 1 increase 10 and percolateDown\n");
	Heap.increaseKey(1, 10);
	Heap.print();
	
	printf("position 1 decrease 15 and percolateUp\n");
	Heap.decreaseKey(1, 15);
	Heap.print();
	
	printf("deleteMin:\n");
	Heap.deleteMin();
	Heap.print();
	
	system("pause");
}