【代码】c++堆的简单实现-创新互联

堆对象的创建与实现的核心思想就是上调(adjustup)与下调(adjustdown)的算法思想,上调用于创建堆时,从第一个非叶子节点开始向根节点根据需求调整为大堆或者小堆

成都创新互联是一家专注于成都网站设计、成都网站建设、外贸网站建设与策划设计,玉州网站建设哪家好?成都创新互联做网站,专注于网站建设十多年,网设计领域的专业建站公司;建站业务涵盖:玉州等地区。玉州做网站价格咨询:18980820575

    下调如图示:

【代码】c++堆的简单实现

    当我们进行插入时,会影响堆的结构,这时我们用尾插,然后上调如图示:

【代码】c++堆的简单实现

    接下来就可以创建堆类,代码如下仅供参考:

#include
#include
template 
struct CompMax
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};
template 
struct CompMin
{
	bool operator()(const T& a,const T& b)
	{
		return a < b;
	}
};

template  >//仿函数做模板参数,可根据需求修改比较方法
class Heap
{
public:
	Heap(const T* arr, size_t size, Com _comp)
		:comp(_comp)
	{
		_List.resize(size);
		int index = 0;
		for (index = 0; index < size; ++index)
		{
			_List[index] = arr[index];
		}
		index = (_List.size()- 2) / 2;
		while (index>=0)
			_adjustdown(index--);

	}
	void Push(const T &x)
	{
		_List.push_back(x);
		size_t index = _List.size() - 1;
		_adjustup(index);
	}
	void Pop()
	{
		_List.pop_back();
	}
	T& Top()
	{
		return _List[0];
	}
protected:
	void _adjustup(size_t index)
	{
		size_t child = index;
		size_t parent = (child - 1) / 2;
		while (child)
		{
			if (child % 2)
			{
				if (child + 1<_List.size())
					child =comp(_List[child],_List[child+1]) ? child : child + 1;
			}
			else
			{
				child = comp(_List[child] ,_List[child - 1]) ? child : child - 1;
			}
			if (!comp(_List[child],_List[parent]))
			{
				std::swap(_List[parent], _List[child]);
			}
			child = parent;
			parent = (parent - 1) / 2;

		}
	}
	void _adjustdown(size_t index)
	{
		size_t parent = index;
		size_t child = parent * 2 + 1;
		while (child < _List.size())
		{
			if (child + 1 < _List.size())
				child = comp(_List[child] , _List[child + 1]) ? child : child + 1;
			if (!comp(_List[parent], _List[child]))
			{
				std::swap(_List[child], _List[parent]);
				parent = child;
				child = (parent + 1) * 2;
			}
			else
				break;
		}

	}
protected:
	vector _List;
	Com comp;
};

    如有不足希望指正,如有问题也希望提出,谢谢-3-。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


本文标题:【代码】c++堆的简单实现-创新互联
网页URL:http://scyanting.com/article/dhgpsd.html