在二叉樹中，我們用兩種方法表示二叉樹，一個(gè)是鏈表，一個(gè)是數(shù)組，但是數(shù)組比較適用于滿二叉樹或者完全二叉樹。

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),石阡企業(yè)網(wǎng)站建設(shè),石阡品牌網(wǎng)站建設(shè),網(wǎng)站定制,石阡網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,石阡網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

    堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對(duì)象，它可以被視為一棵完全二叉樹結(jié)構(gòu)。

    堆結(jié)構(gòu)的二叉樹存儲(chǔ)有兩種方法：

        最大堆：每個(gè)父節(jié)點(diǎn)的都大于孩子節(jié)點(diǎn)。

        最小堆：每個(gè)父節(jié)點(diǎn)的都小于孩子節(jié)點(diǎn)。

#include
#include
#include

using namespace std;

template
class Heap
{
public:
	Heap()//無(wú)參類型的構(gòu)造函數(shù)
	{}
	Heap(T *a, size_t size)//有參類型的構(gòu)造函數(shù)
	{
		assert(a);
	
		for (size_t i = 0; i < size; i++)
		{
			_a.push_back(a[i]);
		}
		//建堆，用 向下調(diào)整 算法
		//對(duì)于一個(gè)完全二叉樹，其結(jié)點(diǎn)的父子關(guān)系與數(shù)組的下標(biāo)的關(guān)系：
		//左子下標(biāo)= 父結(jié)點(diǎn)下標(biāo)*2+1
		//右子下標(biāo)=父結(jié)點(diǎn)下標(biāo)*2+2
		for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)（最后一個(gè)元素一定是非葉子結(jié)點(diǎn)的子節(jié)點(diǎn)）
		{
			_AdjustDown(j);
		}
		/*
		在第一次寫時(shí)定義了j為size_t類型，由于j不管怎么運(yùn)算都是無(wú)符號(hào)類型所以
		j>=0并沒(méi)有起到限制的作用，導(dǎo)致了死循環(huán)
		*/
	}
public:
	void Push(const T &x)//在最后加入一個(gè)節(jié)點(diǎn)
	{
		_a.push_back(x);
		_AdjustUp(_a.size() - 1);//向上調(diào)整，傳入最后一個(gè)元素下標(biāo)（調(diào)整x的位置）
	}
	
	void Pop()//把最大的刪掉（根）
	{
		assert(!_a.empty());

		swap(_a[0], _a[_a.size() - 1]);//把根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換
		_a.pop_back();//刪掉最后一個(gè)節(jié)點(diǎn)
		_AdjustDown(0);//向下調(diào)整
	}
	
	void Print()
	{
		for (size_t i = 0; i < _a.size(); i++)
		{
			cout << _a[i]<<" ";
		}
		cout << endl;
	}
	size_t size()
	{
		return _a.size();
	}
	bool empty()
	{
		return _a.empty();
	}
protected:
	void _AdjustDown(size_t parent)//時(shí)間復(fù)雜度O(log2(N))
	{
		size_t child = parent * 2 + 1; //找到其左孩子
		while (child < _a.size())
		{
			if ((child + 1) < _a.size() && _a[child] < _a[child + 1])//若左孩子小于右孩子（且必須結(jié)點(diǎn)下標(biāo)不超過(guò)范圍）
			{
				++child;//指向大的
			}
			if (_a[child]>_a[parent])//若孩子大于父，則把大的放在父結(jié)點(diǎn)上
			{
				swap(_a[child], _a[parent]);
				parent = child;//父和子調(diào)整后要繼續(xù)向下調(diào)整交換后的子節(jié)點(diǎn)
				child = parent * 2 + 1;//現(xiàn)在這個(gè)調(diào)整后的節(jié)點(diǎn)的子節(jié)點(diǎn)
			}
			else
				break;
		}
	}
	
	void _AdjustUp(size_t child)//時(shí)間復(fù)雜度O(log2(N))
	{
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_a[child] > _a[parent])
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
		
	}
private:
	vector _a;
};

測(cè)試函數(shù)

void test()
{
	int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
	Heap h2(a, 10);
	h2.Push(3);
	h2.Push(4);
	h2.Print();
	h2.Push(100);
	h2.Print();
	h2.Pop();
	h2.Print();
	h2.Pop();
	h2.Print();

}
int main()
{
	test();
	getchar();
	return 0;
}

    上面實(shí)現(xiàn)了最大堆，最小堆方法同最大堆，但是再在類中重新一遍則會(huì)使程序的可維護(hù)性降低，所以我們用仿函數(shù)來(lái)實(shí)現(xiàn)。

仿函數(shù)

仿函數(shù)就是使一個(gè)類使用看上去像一個(gè)函數(shù)，其實(shí)現(xiàn)就是類中實(shí)現(xiàn)一個(gè)operator().這個(gè)類就有了類似函數(shù)的行為。

用仿函數(shù)實(shí)現(xiàn)最大堆與最小堆

template
struct Less
{
	bool operator()(const T&left, const T&right)
	{
		return left < right;
	}
};
template
struct Greater
{
	bool operator()(const T&left, const T&right)
	{
		return left>right;
	}
};

template>
class Heap
{
public:
	Heap()//無(wú)參類型的構(gòu)造函數(shù)
	{}
	Heap(T *a, size_t size)//有參類型的構(gòu)造函數(shù)
	{
		assert(a);
	
		for (size_t i = 0; i < size; i++)
		{
			_a.push_back(a[i]);
		}
		//建堆，用 向下調(diào)整 算法
		//對(duì)于一個(gè)完全二叉樹，其結(jié)點(diǎn)的父子關(guān)系與數(shù)組的下標(biāo)的關(guān)系：
		//左子下標(biāo)= 父結(jié)點(diǎn)下標(biāo)*2+1
		//右子下標(biāo)=父結(jié)點(diǎn)下標(biāo)*2+2
		for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)（最后一個(gè)元素一定是非葉子結(jié)點(diǎn)的子節(jié)點(diǎn)）
		{
			_AdjustDown(j);
		}
	}
public:
	void Push(const T &x)//在最后加入一個(gè)節(jié)點(diǎn)
	{
		_a.push_back(x);
		_AdjustUp(_a.size() - 1);//向上調(diào)整，傳入最后一個(gè)元素下標(biāo)（調(diào)整x的位置）
	}
	void Pop()//把最大的刪掉（根）
	{
		assert(!_a.empty());

		swap(_a[0], _a[_a.size() - 1]);//把根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換
		_a.pop_back();//刪掉最后一個(gè)節(jié)點(diǎn)
		_AdjustDown(0);//向下調(diào)整
	}
	void Print()
	{
		for (size_t i = 0; i < _a.size(); i++)
		{
			cout << _a[i]<<" ";
		}
		cout << endl;
	}
	size_t size()
	{
		return _a.size();
	}
	bool empty()
	{
		return _a.empty();
	}
protected:
	void _AdjustDown(size_t parent)//時(shí)間復(fù)雜度O(log2(N))
	{
		size_t child = parent * 2 + 1; //找到其左孩子
		compare com;
		while (child < _a.size())
		{
			if ((child + 1) < _a.size() && com(_a[child+1],_a[child]))
			{
				++child;
			}
			if (com(_a[child],_a[parent]))//
			{
				swap(_a[child], _a[parent]);
				parent = child;//父和子調(diào)整后要繼續(xù)向下調(diào)整交換后的子節(jié)點(diǎn)
				child = parent * 2 + 1;//現(xiàn)在這個(gè)調(diào)整后的節(jié)點(diǎn)的子節(jié)點(diǎn)
			}
			else
				break;
		}
	}
	void _AdjustUp(size_t child)//時(shí)間復(fù)雜度O(log2(N))
	{
		size_t parent = (child - 1) / 2;
		compare com;
		while (child > 0)
		{
			if (com(_a[child] , _a[parent]))
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
		
	}
private:
	vector _a;
};

    這樣就實(shí)現(xiàn)了最大堆與最小堆，通過(guò)仿函數(shù)，程序的可維護(hù)性好于在類中寫一個(gè)最大堆寫法和最小堆寫法。

測(cè)試

void test1()
{
	int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
	int b[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
	Heap> h2(a, 10);//最小堆
	h2.Push(3);
	h2.Push(4);
	h2.Print();
	h2.Push(100);
	h2.Print();
	h2.Pop();
	h2.Print();
	h2.Pop();
	h2.Print();
	
	Heaph3(b);//最大堆
        h3.Push(3);
	h3.Push(4);
	h3.Print();
	h3.Push(100);
	h3.Print();
	h3.Pop();
	h3.Print();
	h3.Pop();
	h3.Print();
}

堆的應(yīng)用：

1.堆排序

分析：由于在大堆或者小堆排完后，只能保證每個(gè)小樹為大堆或者小堆，故還需要進(jìn)行排序才能使數(shù)組元素完全依次排列。

      所以我們先用大堆排列后，使堆頂元素為大元素，再依次將堆頂元素和未交換的最后一個(gè)元素交換，交換完成后再將除了大的元素之外的元素進(jìn)行交換

/******************************
堆排序
盡建立一個(gè)大堆，每次把堆頂?shù)脑睾妥詈笠粋€(gè)還未交換的元素交換
*/
void AdjustDown(int *a, int parent, int size)
{
	int child = parent * 2 + 1;
	
	while (child < size)
	{
		if (a[child] a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;

	}
}
void HeapSort(int *a, int n)
{
	assert(a);

	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a,i,n);//大堆向下調(diào)整
	}
	
	for (int i = 0; i < n; i++)
	{
		swap(a[n - 1 - i],a[0]);
		AdjustDown(a, 0, n - 1 - i);
	}

}

2.求N個(gè)元素中前K個(gè)最大的數(shù)

    分析：建立一個(gè)小堆存放前K個(gè)元素，小堆的堆頂元素為前K個(gè)中最小的值，剩下N-K個(gè)數(shù)中依次和堆頂元素相比較，若大于堆頂元素，入堆，每入堆一個(gè)元素再小堆排序一次，使堆頂元素總為這K個(gè)元素的最小值；若小于堆頂元素，則繼續(xù)下一個(gè)數(shù)比較。當(dāng)N-K個(gè)元素全比較完，堆中這K個(gè)元素就是最大的前K個(gè)數(shù)。

/*
從N個(gè)數(shù)中找到K個(gè)最大的數(shù)
建立一個(gè)小堆，大小為K,每次從第N-K的數(shù)據(jù)中取出一個(gè)和堆頂元素比較
*/
const int N = 1000000;
const int K = 100;

void AdjustDown(int *a, int parent, int size)
{
	int child = parent * 2 + 1;
	while (child  a[child + 1])
		{
			child++;
		}
		
		if (a[child] < a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
void GetTopK(int *a)
{
	assert(K < N);
	int top[100];

	for (size_t i = 0; i < 100; i++)
	{
		top[i] = a[i];
	}
	//建一個(gè)小堆，向下調(diào)整
	for (int i = (K - 2) / 2; i>=0; i--)
	{
		AdjustDown(top, i, K);
	}
	//從剩下的N-K的數(shù)據(jù)中拿數(shù)據(jù)和堆頂元素比較，若小于堆頂元素，則入堆
	for (size_t j = K; j < N ; j++)
	{
		if (a[j]            
            
                        

            網(wǎng)站題目：堆的結(jié)構(gòu)分析與應(yīng)用            

            文章路徑：http://weahome.cn/article/jsgjhe.html