学步园

make_heap函数用来从给定的任意顺序的数组创建一个最大堆。

push_heap函数向堆中压入一个新的数据，并维持堆的形态。

pop_heap函数取出堆中最大的元素，并将该元素从堆结构中剔除，维持堆的形态。

使用了定长数组作为基本的存储数据的结构，当数组空间满时，重新申请一个两倍长于当前数组的新数组，将元素复制过去。

heap.cpp

class heap
{
private:
	int *_A;
	int _size;	//当前元素数量
	int _max_size;	//所能容纳的最大数量
	void _adjust_heap(int i)
	{
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		int largest;
		//选出三个节点中最大的元素，将他放到根节点中
		if(left <= _size - 1 && _A[left] > _A[i])
			largest = left;
		else
			largest = i;

		if(right <= _size - 1 && _A[right] > _A[largest])
			largest = right;

		if(largest != i)
		{
			int tmp = _A[i];
			_A[i] = _A[largest];
			_A[largest] = tmp;

			_adjust_heap(largest);
		}
	}
	void _double_heap()
	{
		int *tmp = new int[_size * 2];
		for(int i = 0; i < this->_size; i++)
			tmp[i] = this->_A[i];	//复制到新的空间中
		delete _A;
		this->_A = tmp;  

		_max_size = _size * 2;
	}
	
public:
	void make_heap(int *B, int size)
	{
		this->_A = new int[size];
		for(int i = 0; i < size; i++)
			this->_A[i] = B[i];
		this->_size = size;
		this->_max_size = size;

		//从后往前依次调整堆结构，使得成为最大堆
		int end = _size/2 - 1;
		for(int i = end; i > 0; i--)
			_adjust_heap(i);
	}
	void push_heap(int element)
	{
		if(_size == _max_size)	//堆数组满
			_double_heap();
		this->_A[_size] = element;
		this->_size++;
		_adjust_heap(0);
	}
	int pop_heap()
	{
		//交换最大的元素（第一个）和最后一个元素的位置，并将堆大小减一
		int tmp = this->_A[0];
		this->_A[0] = this->_A[this->_size - 1];
		this->_A[this->_size - 1] = tmp;
		this->_size--;

		_adjust_heap(0);	//从首元素开始调整堆结构
		return tmp;
	}
};

test.cpp

#include <iostream>
#include "heap.cpp"
using namespace std;

int main()
{
	heap p;
	int A[10] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
	p.make_heap(A, 10);
	p.push_heap(13);
	for(int i = 0; i < 10; i++)
		cout<<p.pop_heap()<<" ";
}

最小堆的使用实例：

Find_Top_K问题：数组N中寻找最大的K个元素：

用前K[0...k-1]个元素，建立小顶堆K-Min-Heap；

遍历K...N-1元素，和堆顶元素比较：

小于跳过，

大于则替换堆顶元素，调整K-Min-Heap结构使之保持小顶堆特性；

K-Heap的操作时间为log2(k)

插入法建堆和上面代码中使用的调整法建堆效率是有差距的，插入法建堆指的是从一个元素的堆开始，依次向堆中插入数据，并调整堆，最后得到最大堆。调整法建堆的时间复杂度为：O(n)，而插入法建堆的最坏时间复杂度为：O(nlgn)