一. 二叉堆的性质

  堆是一种具有堆序性的完全二叉树.

  作为一种完全二叉树, (假定空树的高度是-1)它的高度是floor(logN), 高度为h的结点有2^h到2^(h+1) - 1个, 父节点的下标为floor(i/2), 左孩子的下标为2i, 右孩子的下标为2i+1

  而所谓堆序性就是(以最小堆为例)父节点总是小于孩子节点的性质. 由此可以得出两个推论:

  1) 堆顶元素是最小元素

  2) 结点的左右子树仍是最小堆

二. 最小堆的抽象数据类型(ADT)

   底层容器可以选择动态数组, vector等随机访问容器. 为了方便取下标, 容器的第0位作为哑节点不予使用.

   最小堆的抽象数据类型如下:

  1: class BinaryHeap
  2: {
  3: private:
  4: 	vector<int> heap;
  5: 
  6: 	void buildHeap();          //将数组原址堆化
  7: 	void adjustDown(int node); //下沉
  8: 	void adjustUp(int node);   //上浮
  9: 
 10: public:
 11: 	explicit BinaryHeap()      //构建一个空堆
 12: 	{
 13: 		heap = vector<int>(); 
 14: 		heap.push_back(0);
 15: 	}
 16: 	explicit BinaryHeap(const vector<int>& items); //从已有数组建堆
 17: 
 18: 	void insert(const int key); //插入
 19: 	void removeMin();           //移除堆顶元素
 20: 
 21: 	void decreaseKey(int pos, unsigned int delta);
 22: 	void increaseKey(int pos, unsigned int delta);
 23: 	void removeKey(int pos);
 24: 
 25: 	bool isEmpty() const { return heap.size() <= 1; }
 26: 	int size() const { return heap.size() - 1; }
 27: 	void traverse();
 28: 	const int min() const { return heap[1]; }
 29: };
 30: 
 31: 

三. 插入和上浮操作

  插入新节点的时候, 首先把节点添加到动态数组的尾部, 即按照层序从左至右填充二叉树. 然后循环比较该节点和父节点, 如果该节点比父节点小, 那么和父节点交换, 直到满足堆序性为止.

考虑到乘2, 除2是计算机的移位运算, 可以用移位运算符来提高性能(但是这种提高很有限).

  1: void BinaryHeap::insert(const int key)
  2: {
  3: 	heap.push_back(key);
  4: 	int hole = heap.size() - 1;
  5: 	adjustUp(hole);
  6: }
  7: 
  8: /*
  9:  * @param node:待处理结点的下标
 10:  */
 11: void BinaryHeap::adjustUp(int node)
 12: {
 13: 	for (; node > 1 && heap[node] < heap[node >> 1]; node >>= 1)
 14: 	{
 15: 		swap(heap[node >> 1], heap[node]);
 16: 	}
 17: }

四. 弹出顶部和下沉操作

弹出顶部时, 把最后一个结点的值赋给堆顶结点, 然后循环比较该节点和左右孩子中较小的一个, 如果大于孩子节点就交换两个结点, 直至该节点小于孩子节点.

  1: void BinaryHeap::removeMin()
  2: {
  3: 	if (isEmpty())
  4: 		throw "Underflow";
  5: 
  6: 	heap[1] = heap[heap.size() - 1];
  7: 	heap.pop_back();
  8: 	adjustDown(1);
  9: }
 10: 
 11: /*
 12:  * @param node 待处理结点
 13:  */
 14: void BinaryHeap::adjustDown(int node)
 15: {
 16: 	int child;
 17: 	int tmp = heap[node];
 18: 
 19: 	for (; (node << 1) <= size(); node = child)
 20: 	{
 21: 		// 寻找左右孩子中较小的一个
 22: 		child = node << 1;
 23: 		// 如果右孩子存在, 且小于左孩子
 24: 		// (完全二叉树的节点不总是存在两个孩子)
 25: 		if (child < size() && heap[child + 1] < heap[child])
 26: 			++child;
 27: 		// 如果这个孩子小于父亲
 28: 		if (heap[child] < tmp)
 29: 			swap(heap[node], heap[child]);
 30: 		else break;
 31: 	}
 32: }

需要注意的是, 被下沉的结点不一定下沉到最后一层, 有可能下沉到倒数第二层.

五. 堆化数组操作

基本思路是从倒数第二层起, 自底向上执行adjustDown操作. 这样做的目的是实现二叉堆的必要条件: 子树为二叉堆. 当adjustDown执行到树根时, 就完成了堆化数组.

  1: BinaryHeap::BinaryHeap(const vector<int>& items)
  2: {
  3: 	heap = vector<int>();
  4: 	heap.push_back(0);
  5: 	for (int i = 0; i < items.size(); ++i)
  6: 	{
  7: 		heap.push_back(items[i]);
  8: 	}
  9: 	buildHeap();
 10: }
 11: 
 12: void BinaryHeap::buildHeap()
 13: {
 14: 	for (int i = size() >> 1; i > 0; i--)
 15: 	{
 16: 		adjustDown(i);
 17: 	}
 18: }

六. 改变结点的值, 同时维护堆序性质

当增加一个节点的值的时候, 如果该节点大于子结点, 就要使该节点下沉. 当减小一个节点的值时, 如果该节点小于父节点, 就要使该节点上浮.

当删除一个节点的时候, 首先让结点变成最小的, 令其上浮到堆顶, 之后deleteMin()

  1: void BinaryHeap::decreaseKey(int pos, unsigned int delta)
  2: {
  3: 	if (pos<1 || pos>size())
  4: 		throw "ArrayIndexOutOfBoundsException";
  5: 	heap.at(pos) -= delta;
  6: 	adjustUp(pos);
  7: }
  8: 
  9: void BinaryHeap::increaseKey(int pos, unsigned int delta)
 10: {
 11: 	if (pos<1 || pos>size())
 12: 		throw "ArrayIndexOutOfBoundsException";
 13: 	heap[pos] += delta;
 14: 	adjustDown(pos);
 15: }
 16: 
 17: void BinaryHeap::removeKey(int pos)
 18: {
 19: 	decreaseKey(pos, numeric_limits<int>::max());
 20: 	removeMin();
 21: }

二叉堆(Binary Heap)