【数据结构】大小堆的实现及堆排序

堆一般指二叉堆，结构如下

圈内数字指下标，圈外为内容，如图现在并不能称为一个堆，因为它并不满足大堆也不满足小堆的组成，下面介绍大堆和小堆的简答介绍和实现

大堆是指每个父节点的数都大于自己的每个孩子节点的值

用到的算法是让大数上移循环至完成大堆

	void Adjustup(size_t child)
	{
		Compare<T> com;
		size_t parent =(child-1)/2;
		while(child>0)
		{
			if(com(_a[child],_a[parent]))
			{
				swap(_a[parent],_a[child]);
				child=parent;
				parent=(child-1)/2;
			}
			else
			{
				break;
			}
		}
	}

第一次交换33和43；

第二次交换43和12；

第三次交换33和12；

第四次交换23和8；

小堆的算法如下，采用大数向下循环转换

void Adjustdown(size_t parent)
	{

		size_t child =parent*2+1;
		while(child<_a.size())
		{
			Compare<T> com;
		if(child+1<_a.size()&&com(_a[child+1],_a[child]))
		{
			++child;
		}
			if(com(_a[child],_a[parent]))
			{
			swap(_a[parent],_a[child]);
			parent=child;
			child=parent*2+1;
		}
		else
		{
			break;
		}
		}
	}

第一次交换33和5，

第二次交换12和5，

第三次交换4和8，

第四次交换5和4

堆排序算法如下

 void HeapSort(T* a,size_t size)
	{
		_a.reserve(size);
		for(size_t i=0;i<size;i++)
		{
			_a.push_back(a[i]);
		}
		for(int i=(_a.size()-2)/2;i>=0;--i)
		{
			Adjustdown(i);
		}
		print(_a,size);
	}

#include <iostream>
#include <assert.h>
#include<stdlib.h>
#include <vector>
using namespace std;
template<typename T>
struct Big
{
	bool operator()(const T& l,const T& r)
	{
		return l>r;
	}
};
template<typename T>
struct Less
{
	bool operator()(const T& l,const T& r)
	{
		return l<r;
	}
};
template<class T,template<class> class Compare>
class Heap//二叉堆
{

public:
	Heap()
	{}
    void HeapSort(T* a,size);
	}
	void Adjustup(size_t child)
	{
		Compare<T> com;
		size_t parent =(child-1)/2;
		while(child>0)
		{
			if(com(_a[child],_a[child]);
				child=parent;
				parent=(child-1)/2;
			}
			else
			{
				break;
			}
		}
	}
	void Adjustdown(size_t parent)
	{

		size_t child =parent*2+1;
		while(child<_a.size())
		{
			Compare<T> com;
		if(child+1<_a.size()&&com(_a[child+1],_a[child]);
			parent=child;
			child=parent*2+1;
		}
		else
		{
			break;
		}
		}
	}
	bool Empty()
	{
		return _a.size()==0;
	}
	T& top()
	{
		assert(!_a.empty());
		return _a[0];
	}
	void Push(const T& x)
	{
	 _a.push_back(x);
	 size_t _size=_a.size();
	 Adjustup(_size-1);
	 print(_a,_size);
	}
	void Pop()
	{
		size_t _size=_a.size();
		assert(_size>0);
		swap(_a[0],_a[_size-1]);
		_a.pop_back();
		_size=_a.size();
		Adjustdown(0);
		print(_a,_size);
	}
   void print(vector<T> a,size_t size)
   {

	   for(int i=0;i<size;i++)
	   {
		   cout<<a[i]<<" ";
	   }
	   cout<<endl;
   }
private:
	vector<T> _a;
};

void test()
{
	int Tree[]={23,12,33,45,15,46,17,78,59};
	Heap<int,Big> h1; 
	h1.HeapSort(Tree,sizeof(Tree)/sizeof(Tree[0]));
}
void test2()
{
	int arr[] = { 12,10,43,23,22,67,9 };
	Heap<int,Big>   h1;
	h1.HeapSort(arr,sizeof(arr)/sizeof(arr[0])); 
	Heap<int,Less>  h2;
	h2.HeapSort(arr,sizeof(arr)/sizeof(arr[0])); 
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!