[算法导论]最大堆

堆数据结构市一中数组对象，它可以被视为一棵完全二叉树。其中最大堆或者最小堆在堆排序以及求TOP N类型的问题中都有着广泛的应用。

对与堆中的节点i来说，它的父节点是索引i/2,左孩子的索引是2*i,右孩子的索引是2*i+1。

max_heapify函数的第一个参数是整个堆所在的数组，第二个参数是当前节点的索引i，也可以看成对 以当前节点i为根节点的堆进行最大堆化，该过程首先是从（当前节点i,左孩子2*i，右孩子2*i+1）中找出其中对大的那个元素的索引largest，如果这个索引不是当前节点，那么就需要交换当前节点和最大值节点的内容，交换数据内容之后，以索引largest为根节点的堆可能不是最大堆，所以需要紧接着重新继续调用max_heapify。

build_max_heap则是以一种自底向上的方式建立最大堆，之所以使用这种方式，私以为，是因为为了更好的利用max_heapify，减少max_heapify的调用次数。

其中需要注意的是，这里的数组中的index需要1开始，数组中的第一个（0）元素-1是为了占用一个位置。

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

#define PARENT(i) (i/2)
#define LEFT(i)   (2*i)
#define RIGHT(i) (2*i+1)


void max_heapify(vector<int> &A,int i)
{
	int largest=i; //first, we assume i is the max number's index
	int l=LEFT(i); //left child's index
	int r=RIGHT(i); //right child's index

	//find max element's index  in (parent,left,child)

	if (l<A.size() && A[l]>A[i])
	{
		largest=l;
	} 
	if (r<A.size() && A[r]>A[largest])
	{
		largest=r;
	}

	if (largest!=i) // if current parent is not the largest one , then 
	{
		swap(A[largest],A[i]);
		max_heapify(A,largest);
	}
}
void build_max_heap(vector<int> &A)
{
	int length=A.size()-1;
	for (int i = length/2 ; i >=0; i--)
	{
		max_heapify(A,i);
	}
}

//

void test_max_heap()
{
	int a[]={-1,4,1,3,2,16,9,10,14,8,7};
 	vector<int> A(a,a+11);
 	vector<int>::iterator iter ;
 	for ( iter=A.begin()+1; iter!=A.end(); iter++)
 	{
  		cout<<*iter<<"\t";
 	}
 	cout<<endl;
 	build_max_heap(A);
 	for ( iter=A.begin()+1; iter!=A.end(); *iter++)
 	{
 		cout<<*iter<<"\t";
 	}
 	cout<<endl;

}

int main()
{
	test_max_heap();
	cin.get();
}