频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
堆结构:最大堆
2016-10-12 09:13:57      个评论    来源:poison_biti的博客  
收藏   我要投稿

“test.cpp”

#include
using namespace std;
#include
template
class Heap
{
public:
	Heap(T* arr,size_t size)
	{
		_arr.reserve(size);
		
		for(size_t i = 0;i < size;i++)
		{
			_arr.push_back(arr[i]);
		}
		
		//数组建堆
		for(int i = (_arr.size()-2)/2;i >= 0;--i)
		{
			AdjustDown(i);
		}
	}

	void Push(const T& data)
	{
		_arr.push_back(data);
		AdjustUp(_arr.size()-1);
	}
	//pop掉堆顶的数据
	void Pop()
	{
		//先使堆顶数据和最后一个数据交换,然后吧最后一个数据pop掉
		swap(_arr[0],_arr[_arr.size()-1]);
		_arr.pop_back();

		//原先的最后一个数据调至堆顶,然后除堆顶外左右子树还是满足大堆
		//所以此时只需要将堆顶的数据向下调整
		AdjustDown(0);

	}
	void Display()
	{
		for(size_t i = 0;i < _arr.size();i++)
		{
			cout<<_arr[i]<<" ";
		}
		cout< _arr[child])
			{
				++child;
			}

			if(_arr[child] > _arr[parent])
			{
				swap(_arr[child],_arr[parent]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}
	void AdjustUp(size_t root)
	{
		size_t child = root;
		size_t parent = (child-1)/2;

		while(parent >= 0)
		{
			if(_arr[child] > _arr[parent])
			{
				swap(_arr[child],_arr[parent]);
				child = parent;
				parent = (child-1)/2;
			}
			else
			{
				break;
			}
		}
	}
	size_t Size()
	{
		return _arr.size();
	}
	bool Empty()
	{
		return _arr.empty();
	}
	const T& Top()
	{
		return _arr[0];
	}
private:
	vector _arr;
};

void test()
{
	int arr[] = {10,11,13,12,16,18,15,17,14,19};
	int size = sizeof(arr)/sizeof(arr[0]);

	Heap hp(arr,size);
	hp.Display();

	hp.Push(20);
	hp.Display();

	hp.Pop();
	hp.Display();

	cout<<"size = "<
点击复制链接 与好友分享!回本站首页
上一篇:c++使用libiconv
下一篇:c++中的参数传递方式
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站