基础数据结构————堆

更新完了，但是细节说的还不太够，以后再说吧(￣▽￣)／

简单介绍

  堆的本质是一个完全二叉树，除了最下面一层以外，其他的每层（假设第(n)层）都有(2^n)个结点。节点存的值每层都是递增或者递减的。递增的话就是大顶堆，递减的话就是小顶堆。那么对于大顶堆来说，每个节点的儿子节点上的值都要小于等于该节点，否则它就不是一个堆。堆需要维护所有元素中的最大（小）值，我们可以用堆来实现优先队列。

算法设计

堆常用的操作有两个：添加元素，删除堆顶元素。不过在此之前我们要先看看对于给定的一个序列，我们如何建堆。

建树

假定我们下面说的堆都是大顶堆。我们可以很清楚的发现，对于一个堆的子树而言，它也必然满足所有节点的儿子结点都小于等于它。也就是说这个子树也是一个堆，那么我们在建树的时候考虑率需要考虑每个节点和它儿子结点的大小，如果不满足父节点最大，就要将左右儿子节点中较大的那个和父节点交换。即保证父节点是最大的，儿子节点哪个小我们并不关心。

这样考虑的话我们可以从堆的下面网上遍历，对于叶子结点而言我们不必考虑。然后我们比较每个结点和它两个（或者一个）儿子结点。如果儿子结点更大，那么将其和父节点交换。但是这样交换的话，儿子结点会换的更小，那么久无法保证下面的结构也满足堆了，所以这里我们还需要继续向下搜儿子结点的儿子结点，直到叶子结点。这样才能保证每次从上面换下来的小一点的结点能到它该去的地方。我们将这个操作写成一个函数，取名ShiftDown()

这个图是百度上面的，看一看就知道是如何建堆的了。。

插入和删除

对于插入和删除操作我们并不像传统的序列操作一样找到目标位置插入或删除再调整。具体的操作步骤如下

插入：将新的值插入到堆的尾部，也就是完全二叉树的最后一个节点的下一个位置。从该位置开始，从下往上调整，如果子节点的值更小，就将其和父节点交换。直到根节点也就是堆顶为止。这个操作我们取名ShiftUp()

删除：这里的删除操作指的是弹出堆顶的那个最大值。这样我们可以用最后一个节点替换堆顶，然后从堆顶往下更新，因为我们只需要保证父节点的值大于子节点，所以只需要跟它的儿子节点比较即可。这个操作其实就是我们刚刚说的ShiftDown().

具体实现

因为写成了一个类，所以就直接在注释里写了

#include<iostream>
using namespace std;

template<typename T>
class Heap
{
public:
	Heap() {}
	Heap(T *a, int num);
	~Heap() { delete heap; }
	T top() { return heap[0]; }
	void pop();
	void push(const T &x);
	int size()const { return currentSize; }
private:
	void ShiftDown(int start);
	void ShiftUp(int start);
	T *heap;
	int currentSize;
};

template<typename T>
Heap<T>::Heap(T *a, int num)
{
	heap = new T[num];	//内存分配
	for (int i = 0; i < num; i++) heap[i] = a[i];	//获取数据
	currentSize = num;
	int currentPos = (num - 2) / 2;	//得到最后一个非叶子结点
	//从这结点开始往上更新，直到叶子结点
	while (currentPos>=0) { ShiftDown(currentPos); currentPos--; }
}

template<typename T>
void Heap<T>::ShiftDown(int start)
{
	int i = start, j = start * 2 + 1;//i是父节点，j是左儿子
	T tmp = heap[i];//用于交换的中间变量，保存的是最初的父节点的值
	while (j < currentSize)
	{
		//如果j<currentSize-1那么保证有右儿子
		if (j + 1 < currentSize&&heap[j] < heap[j + 1]) j++;
		//父节点最大了，就可保证以该节点为根结点的子树，一定满足堆的性质，因为我们是从下往上shiftDown的
		if (heap[i] >= heap[j])break;
		else { heap[i] = heap[j]; i = j; j = 2 * j + 1; }
	}
	//循环退出要么是因为父节点已经最大了，要么是因为比到叶子结点了
	//1.对于前者，我们已经让更大的子节点覆盖到了父节点中，那么heap[i]应该是换上去的较大值，
	//  换完了以后这里应该保存最开始的父节点的较小值，所以我们需要将其赋值为tmp
	//2.对于后者，既然已经到了叶子结点，说明这个叶子结点还比我们当初的父节点的值更大，所以依然同上
	heap[i] = tmp;
}

template<typename T>
void Heap<T>::ShiftUp(int start)
{
	int j = start;//儿子结点，一开始是我们要调整的叶子结点
	int i = (j - 1) / 2; //j的父节点
	T tmp = heap[j];	 //tmp保存我们要调整的那个值
	while (j > 0)
	{
		if (heap[i] >= tmp) break;	//如果当前的父节点已经大于等于儿子结点了那么就不需要调整了
		else { heap[j] = heap[i]; j = i; i = (i - 1) / 2; }	//否则继续向上延伸
	}
	//最后调整完了以后将我们开始的值存入目的位置
	heap[j] = tmp;
}

template<typename T>
void Heap<T>::pop()
{
	//将最后一个结点替换堆顶，然后从上往下调整
	heap[0] = heap[currentSize - 1];
	currentSize--;
	ShiftDown(0);
}

template<typename T>
void Heap<T>::push(const T &x)
{
	//将插入的数放在最后一个结点的下一个位置，从下往上调整
	heap[currentSize] = x;
	ShiftUp(currentSize);
	currentSize++;
}

int main()
{
	int a[] = { 1,2,3,4,5 };
	Heap<int> heap(a, 5);
	while (heap.size()) {
		cout << heap.top() << endl; heap.pop();
	}

	heap.push(3);
	heap.push(5);
	heap.push(1);
	heap.push(4);
	cout << "在添加3,5,1,4后堆顶元素是：" << heap.top() << endl;
}