数据结构-----堆的基本操作和应用

                       （一）用仿函数实现大堆小堆

为翠屏等地区用户提供了全套网页设计制作服务，及翠屏网站建设行业解决方案。主营业务为成都做网站、成都网站设计、翠屏网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

堆结构的二叉树存储是

最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。

仿函数(functor)，就是使一个类的使用看上去象一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。
在实现大，小堆的过程中，有些功能的的代码，会在不同的成员函数中用到，想复用这些代码，有两种途径。

 1）公共的函数，这是一个解决方法，不过函数用到的一些变量，就可能成为公共的全局变量，再说为了复用这么一片代码，就要单立出一个函数，也不是很好维护。

 2）仿函数，写一个简单类，除了那些维护一个类的成员函数外，就只是实现一个operator()，在类实例化时，就将要用的，非参数的元素传入类中。

在C++里，我们通过在一个类中重载括号运算符的方法使用一个函数对象而不是一个普通函数

Heap.h

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

用仿函数实现大堆，小堆的基本结构

#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);
		//将数组中的数据压入栈中
		for(i=0;i=0;i--)
		{
		//向下调整
		_AdjustDown(i);
		}
	}
	//向堆中插入数据
	void push(const T& x)
	{
	_a.push_back (x);
	_Adjustup(_a.size()-1)
	}
/********************
在弹出的时候使用的方法是
先将完全二叉树的根节点与最后一个叶子节点交换，
弹出当前的叶子节点,然后在向下调整
************************/
	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;
			}
			//如果孩子大于父亲则交换继续往下调整
			if(com(_a[child],_a[parent]))
			{
			swap(_a[child],_a[parent]);
			parent=child;
			child=2*parent+1;
			}
			//否则满足大根堆，退出循环
			else
			{
			break;
			}
		}
	
	}

	//向上调整
	void _Adjustup(size_t child)
	{
		 size_t parent=(child-1)/2;
		 while(child>0)//不能写成while(parent>0),因为child为size_t 类型，会构成死循环
		 {
			 Comper com;
			 //如果插入的子节点大于根节点，则交换
			 if(com(_a[child],_a[parent]))
			 {
			 swap(_a[child],_a[parent]);
			 child=parent;
			 parent=(child-1)/2;
			 }
			 //否则满足大堆，退出循环
			 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);
	}
	//选出一个数据交换到末尾,利用帅选法将前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
            
            
                            

                新闻名称：数据结构-----堆的基本操作和应用                

                当前URL：http://dzwzjz.com/article/jjseii.html