堆的实现（堆的建立及push、pop元素）-创新互联

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

堆结构的二叉树存储：

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

建堆：由于堆被视为完全二叉树，故在h-1层找到第一个（从后往前找）非叶子结点，进行堆的下调

建大堆时，从下往上依次判断并调整堆，使该结点的左右子树都满足大堆

建小堆时，从下往上依次判断并调整堆，使该结点的左右子树都满足小堆

可见大堆的建立与小堆的建立方式类似，下面以大堆进行讨论。

利用vactor模板存储堆中元素

template
class Heap
{
public:
	Heap();
	Heap(const T* a, size_t size);
	void Push(const T& x);
	void Pop();
	T& GetTop();//访问堆顶元素
	bool Empty();//判空
	size_t Size();//堆元素个数
	void PrintHeap();
protected:
	void _AdjustDown(size_t Parent);//下调--建大堆(每个父结点都大于孩子结点)
	void _AdjustUp(size_t Child);//上调--建小堆(每个父结点都小于孩子结点)
private:
	vector _a;
};

实现堆的建立

template
Heap::Heap()
:_a(NULL)
{}
template
Heap::Heap(const T* a, size_t size)
{
	assert(a);
	_a.reserve(size);//初始化_a(vector模板的使用)
	for (size_t i = 0; i < size; ++i)
	{
		_a.push_back(a[i]);
	}
	////堆的第一个非叶子结点的数组下标时((size-1)-1)/2（最后一个结点是size-1）
	for (int i = (int)(size - 2) / 2; i >= 0; --i)//不能定义为size_t（无符号）
	{
		_AdjustDown(i);
	}
	//建小堆，类似建大堆的方式，从下向上进行调整堆，使该结点处的左右子树都满足小堆
	//在进行调小堆时，也通过下调实现
}
//下调--建大堆/小堆
template
void Heap::_AdjustDown(size_t Parent)
{
	size_t Child = Parent * 2 + 1;
	while (Child < _a.size())
	{//先进行左右结点的比较,使Child为较大的数的下标，然后与父亲结点进行比较，使较大的数据为父亲结点
		if (Child + 1 < _a.size() && _a[Child] < _a[Child + 1])//存在右结点再进行比较
		{
			++Child;
		}
		if (_a[Child] > _a[Parent])//如果子结点大于父亲结点就交换，否则就要跳出循环
		{
			swap(_a[Child], _a[Parent]);
			Parent = Child;
			Child = Parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//在建立小堆时，只需要将比较条件进行改变就可以实现

在已经是大堆或小堆的堆中加入元素使堆仍为大堆，可通过该元素与它的父结点进行比较

ps：由于插入的元素在数组末尾，故需要通过上调进行比较实现堆的大堆或小堆

template
void Heap::_AdjustUp(size_t Child)//上调
{
	size_t Parent = (Child - 1) / 2;//结点为Child的父亲结点为（Child-1）/2
	while (Child > 0)//当Child等于0时以到堆顶，终止循环
	{
		if (_a[Parent] < _a[Child])//直接进行父亲结点和子结点的比较
		{
			swap(_a[Child], _a[Parent]);
			Child = Parent;
			Parent = (Child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
template
void Heap::Push(const T& x)//元素x入堆
{
	//_a.resize(_a.size() + 1);
	//_a[_a.size()-1] = x;
	_a.push_back(x);
	_AdjustUp(_a.size() - 1);
}

堆中pop元素，删除堆顶元素，使堆仍为大堆。

在已经是大堆或小堆的堆中删除堆顶元素，直接删除堆顶元素，造成无法进行大堆或小堆的实现，可通过将第一个元素与最后一个元素进行交换，然后删除最后一个元素，最后通过下调实现大堆或小堆

template
void Heap::Pop()//出堆
{
	size_t size = _a.size();
	assert(size > 0);//断言堆非空
	swap(_a[0], _a[size - 1]);
	_a.pop_back();
	_AdjustDown(0);//从堆顶开始进行下调
}

实现堆的堆顶，判空及堆元素个数

template
T& Heap::GetTop()//访问堆顶元素
{
	return _a[0];
}
template
bool Heap::Empty()//判空
{
	return _a.size() == 0;
}
template
size_t Heap::Size()//堆元素个数
{
	return _a.size();
}
template
void Heap::PrintHeap()
{
	for (size_t i = 0; i < _a.size(); ++i)
	{
		cout << _a[i] << " ";
	}
	cout << endl;
}

测试用例

#include"Heap.hpp"
void Test4()
{
	int arr[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19};
	Heap h(arr, sizeof(arr) / sizeof(arr[0]));
	h.PrintHeap();
	cout << "empty: " << h.Empty() << endl;
	cout << "size: " << h.Size() << endl;
	cout << "gettop: " << h.GetTop() << endl;
	h.Push(20);
	h.PrintHeap();
	h.Pop();
	h.PrintHeap();
}

如果对于上述说明还是不是很清楚，可自己亲手画图分析，存在不足之处请多多指教。

【vector】包含着一系列连续存储的元素, 其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。

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