（一）用仿函數(shù)實現(xiàn)大堆小堆

為翠屏等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及翠屏網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都做網(wǎng)站、成都網(wǎng)站設(shè)計、翠屏網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

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

堆結(jié)構(gòu)的二叉樹存儲是

最大堆：每個父節(jié)點的都大于孩子節(jié)點。

最小堆：每個父節(jié)點的都小于孩子節(jié)點。

仿函數(shù)(functor)，就是使一個類的使用看上去象一個函數(shù)。其實現(xiàn)就是類中實現(xiàn)一個operator()，這個類就有了類似函數(shù)的行為，就是一個仿函數(shù)類了。
在實現(xiàn)大，小堆的過程中，有些功能的的代碼，會在不同的成員函數(shù)中用到，想復(fù)用這些代碼，有兩種途徑。

 1）公共的函數(shù)，這是一個解決方法，不過函數(shù)用到的一些變量，就可能成為公共的全局變量，再說為了復(fù)用這么一片代碼，就要單立出一個函數(shù)，也不是很好維護。

 2）仿函數(shù)，寫一個簡單類，除了那些維護一個類的成員函數(shù)外，就只是實現(xiàn)一個operator()，在類實例化時，就將要用的，非參數(shù)的元素傳入類中。

在C++里，我們通過在一個類中重載括號運算符的方法使用一個函數(shù)對象而不是一個普通函數(shù)

Heap.h

#include   
#include   
  
using namespace std;  
template  
class display  
{  
public:  
    void operator()(const T &x)  
    {  
        cout<());   
      
    return 0;   
}

用仿函數(shù)實現(xiàn)大堆，小堆的基本結(jié)構(gòu)

#include
#include
using namespace std;

template
struct Less//小于
{
	bool operator()(const T&l,const T&r)
	{
	return l
struct Greater
{
	bool operator()(const T&l,const T&r)
	{
	return l>r;
	}
};
template>//默認建大堆
class Heap
{
private:
	vector _a;
public:

	Heap(const T* a,size_t size)
	{
		assert(a);
		//將數(shù)組中的數(shù)據(jù)壓入棧中
		for(i=0;i=0;i--)
		{
		//向下調(diào)整
		_AdjustDown(i);
		}
	}
	//向堆中插入數(shù)據(jù)
	void push(const T& x)
	{
	_a.push_back (x);
	_Adjustup(_a.size()-1)
	}
/********************
在彈出的時候使用的方法是
先將完全二叉樹的根節(jié)點與最后一個葉子節(jié)點交換，
彈出當前的葉子節(jié)點,然后在向下調(diào)整
************************/
	void pop()
	{
	swap(_a[0],_a[_a.size()-1]);
	_a.pop_back ();
	_AdjustDown(0);
	}
	size_t Size()//求堆的大小
	{
	  return _a.size();
	}

	bool Empty()//堆是否為空
	{
	return _a.empty();
	}
protected:
	void _AdjustDown(size_t parent)
	{
		size_t child=2*parent+1;
		while(child<_a.size())
		{
			Comper com;
			//找出兩個孩子中最大的一個
			if(com(_a[child+1],_a[child]) && child+1<_a.size())//因為是完全二叉樹所以右孩子可能不存在
			{
			child=child+1;
			}
			//如果孩子大于父親則交換繼續(xù)往下調(diào)整
			if(com(_a[child],_a[parent]))
			{
			swap(_a[child],_a[parent]);
			parent=child;
			child=2*parent+1;
			}
			//否則滿足大根堆，退出循環(huán)
			else
			{
			break;
			}
		}
	
	}

	//向上調(diào)整
	void _Adjustup(size_t child)
	{
		 size_t parent=(child-1)/2;
		 while(child>0)//不能寫成while(parent>0),因為child為size_t 類型，會構(gòu)成死循環(huán)
		 {
			 Comper com;
			 //如果插入的子節(jié)點大于根節(jié)點，則交換
			 if(com(_a[child],_a[parent]))
			 {
			 swap(_a[child],_a[parent]);
			 child=parent;
			 parent=(child-1)/2;
			 }
			 //否則滿足大堆，退出循環(huán)
			 else
			 {
			 break;
			 }
		 }
	}
};

                                     (二)堆排序 

#define _CRT_SECURE_NO_WARNINGS 1

#include
#include
using namespace std;

//建初堆，大堆
void AdjustDown(int a[],int n,int parent)
{
	int child=parent*2+1;
	while(childa[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,n,i);
	}
	//選出一個數(shù)據(jù)交換到末尾,利用帥選法將前N-i個元素重新帥選建成一個堆
	for(int i=n-1;i>0;i--)
	{
	swap(a[0],a[i]);
	AdjustDown(a,i,0);
	}

}

void test()
{
	int a[8]={98,77,35,62,55,14,35,48};
	int size=sizeof(a)/sizeof(a[0]);
	HeapSort(a,size);
	for(int i=0;i
            
            
                        

            本文標題：數(shù)據(jù)結(jié)構(gòu)-----堆的基本操作和應(yīng)用            

            地址分享：http://weahome.cn/article/jjseii.html