【STL】Heap – TK-Xiong`s Blog

堆…额，Priority Queue 和 Heap Sort 都有对 Heap 的应用。

Heap 不属于STL的容器组件，它是 Priority Queue 的助手，或者说是内部实现。

具体分析不讲解，自己看书…

实现 Heap 用的是 Vector + Heap算法。

实现了插入、删除、取极值等操作

这里主要要讲的是 Heap 算法。

主要还是以下几个算法：

push_heap – 插入元素
pop_heap – 取出元素
sort_heap – 堆排序(要先保证是一个堆)
make_heap – 建立堆(将现有的数据转化为heap)

Push_Heap ：

将新元素放到最下一层叶子节点的从左至右第一个空格处
将新节点与父节点比较，如果比父节点大，就交换位置，否则结束
交换位置后，再将新节点与父节点比较(即到步骤2)
直到没有父节点或者比父节点小为止

具体代码如下：

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,
					  RandomAccessIterator last)
{
	//向下层调用
	//注意此函数被调用时，新元素已经被插入。 
	__push_heap_aux(first, last, distance_type(first), value_type(first));
}

template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first, 
					RandomAccessIterator last, Distance*, T*)
{
	//根据结构特性，新元素必然在容器最尾端，即 last-first-1 
	__push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last-1))); 
}

template <class RandomAccessIterator, class Distance, class T>
void __push_heap(RandomAccessIterator first, Distance holeIndex, 
					Distance topIndex, T value)
{
	Distance parent = (holeIndex - 1) / 2;
	while(holeIndex > topIndex && *(first + parent) < value)
	{
		//尚未到达顶端 && 父节点的值小于新的值
		//对它们进行交换
		*(first + holeIndex) = *(first + parent);	//将新节点值改为父节点值 
		holeIndex = parent;		//提升新节点编号 
		parent = (holeIndex - 1)/2; 	//提升父节点编号 
	}
	*(first + holeIndex) = value;	//赋予新节点值，完成操作 
}

template <class RandomAccessIterator>

inline void push_heap(RandomAccessIterator first,

RandomAccessIterator last)

{

//向下层调用

//注意此函数被调用时，新元素已经被插入。

__push_heap_aux(first, last, distance_type(first), value_type(first));

}

template <class RandomAccessIterator, class Distance, class T>

inline void __push_heap_aux(RandomAccessIterator first,

RandomAccessIterator last, Distance*, T*)

{

//根据结构特性，新元素必然在容器最尾端，即 last-first-1

__push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last-1)));

}

template <class RandomAccessIterator, class Distance, class T>

void __push_heap(RandomAccessIterator first, Distance holeIndex,

Distance topIndex, T value)

{

Distance parent = (holeIndex - 1) / 2;

while(holeIndex > topIndex && *(first + parent) < value)

{

//尚未到达顶端 && 父节点的值小于新的值

//对它们进行交换

*(first + holeIndex) = *(first + parent); //将新节点值改为父节点值

holeIndex = parent; //提升新节点编号

parent = (holeIndex - 1)/2; //提升父节点编号

}

*(first + holeIndex) = value; //赋予新节点值，完成操作

}

可以看到真正的核心代码是在最后一个函数里面…

逻辑也是上面所述，这里就不多说了，看下一个。

Pop_Heap：

首先将根结点与最后一个结点交换，然后去掉根结点，然后调整堆。

调整方法：

从根开始先向下查找，将较大的上调，一直到叶子节点。

然后将先前与根结点交换的最后一个结点赋到这个点

然后再进行一次向上的查找

代码如下：

template <class RandomAccessIterator> 
inline void pop_heap(RandomAccessIterator first,
					RandomAccessIterator last)
{
	__pop_heap_aux(first, last, value_type(first));
}

template <class RandomAccessIterator, class T>
inline void __pop_heap_aux(RandomAccessIterator first,
						RandomAccessIterator last, T*)
{
	__pop_heap(first, last-1, last-1, T(*(last-1)), distance_type(first));
	//pop操作的结果应为底部容器的第一个元素
	//因此，首先设置要调整的值为尾值
	//然后将首值调整到尾节点
	//然后重整 [first,last-1) 使之变为正确的heap
}

template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first,
						RandomAccessIterator last,
						RandomAccessIterator result,
						T value, Distance*)
{
	*result = *first;	//设置尾值为首值，于是尾值就是我们要pop的值
						//然后最后以 pop_back() 取出即可
	
	//重新调整heap，从树根处开始，欲调整的值为value(原尾值)
	__dajust_heap(first, Distance(0), Distance(last - first), value);
	
}

template <class RandomAccessIterator, class Distance, class T>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value)
{
	Distance topIndex = holeIndex;
	Distance secondChild = 2 * holeIndex + 2;//右边子节点
	
	while(secondChild < len)
	{
		//比较左右节点
		if(*(first + secondChild) < *(first + (secondChild - 1)))
		{
			secondChild--;
		}
		//较大节点上移，然后再往下查找
		*(first + holeIndex) = *(first + secondChild);
		holeIndex = secondChild;
		secondChild = 2 * (secondChild + 1);
	} 
	//如果没有右子节点，只有左子节点
	if(secondChild == len)
	{
		*(first + holeIndex) = *(first + (secondChild - 1));
		holeIndex = secondChild - 1;
	} 
	//然后再向上查找一次 (需测试)
	__push_heap(first, holeIndex, topIndex, value);
}

template <class RandomAccessIterator>

inline void pop_heap(RandomAccessIterator first,

RandomAccessIterator last)

{

__pop_heap_aux(first, last, value_type(first));

}

template <class RandomAccessIterator, class T>

inline void __pop_heap_aux(RandomAccessIterator first,

RandomAccessIterator last, T*)

{

__pop_heap(first, last-1, last-1, T(*(last-1)), distance_type(first));

//pop操作的结果应为底部容器的第一个元素

//因此，首先设置要调整的值为尾值

//然后将首值调整到尾节点

//然后重整 [first,last-1) 使之变为正确的heap

}

template <class RandomAccessIterator, class T, class Distance>

inline void __pop_heap(RandomAccessIterator first,

RandomAccessIterator last,

RandomAccessIterator result,

T value, Distance*)

{

*result = *first; //设置尾值为首值，于是尾值就是我们要pop的值

//然后最后以 pop_back() 取出即可

//重新调整heap，从树根处开始，欲调整的值为value(原尾值)

__dajust_heap(first, Distance(0), Distance(last - first), value);

}

template <class RandomAccessIterator, class Distance, class T>

void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value)

{

Distance topIndex = holeIndex;

Distance secondChild = 2 * holeIndex + 2;//右边子节点

while(secondChild < len)

{

//比较左右节点

if(*(first + secondChild) < *(first + (secondChild - 1)))

{

secondChild--;

}

//较大节点上移，然后再往下查找

*(first + holeIndex) = *(first + secondChild);

holeIndex = secondChild;

secondChild = 2 * (secondChild + 1);

}

//如果没有右子节点，只有左子节点

if(secondChild == len)

{

*(first + holeIndex) = *(first + (secondChild - 1));

holeIndex = secondChild - 1;

}

//然后再向上查找一次 (需测试)

__push_heap(first, holeIndex, topIndex, value);

}

记于此- 接下来是 Sort_Heap()，即排序算法。

Sort_Heap：

因为每次pop_heap()可以获得 Heap 中最大的元素，如果持续对整个 Heap 做 pop_heap() 操作，每次将范围从后向前减少一个，当程序执行完毕时，我们就获得了一个递增序列。

代码如下：

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first,
				RandomAccessIterator last)
{
	while(last - first > 1)
	{
		pop_heap(first, last--);
	}
}

template<class RandomAccessIterator>

void sort_heap(RandomAccessIterator first,

RandomAccessIterator last)

{

while(last - first > 1)

{

pop_heap(first, last--);

}

我个人觉得看懂是没难度的。

就是每次将最大值放到最后，然后循环即可…

make_heap：

用算法将现有的数据转化为一个heap…

template<class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first,
					RandomAccessIterator last){
	__make_heap(first, last, value_type(first), distance_type(first));
}

template<class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first,
				RandomAccessIterator last, T*, Distance*){
	//如果长度为0或者1，则不需要重排
	if(last - first < 2) return;
	Distance len = last - first;
	//找到一个需要重排的子树头部，依次重排即可。
	Distance parent = (len - 2) / 2;
	while(1)
	{
		__adjust_heap(first, parent, len, T(*(first+parent)));
		if(parent == 0) return;
		parent--;
	}
}

template<class RandomAccessIterator>

inline void make_heap(RandomAccessIterator first,

RandomAccessIterator last){

__make_heap(first, last, value_type(first), distance_type(first));

}

template<class RandomAccessIterator, class T, class Distance>

void __make_heap(RandomAccessIterator first,

RandomAccessIterator last, T*, Distance*){

//如果长度为0或者1，则不需要重排

if(last - first < 2) return;

Distance len = last - first;

//找到一个需要重排的子树头部，依次重排即可。

Distance parent = (len - 2) / 2;

while(1)

{

__adjust_heap(first, parent, len, T(*(first+parent)));

if(parent == 0) return;

parent--;

}

然后要注意的是： Heap没有迭代器。

最后做一个测试文档：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	//底层以Vector完成的Heap 
	int ia[9] = {0,1,2,3,4,8,9,3,5};
	vector<int> ivec(ia,ia+9);
	
	//0 1 2 3 4 8 9 3 5
	for(int i=0;i<ivec.size();i++)
		cout << ivec.at(i) << " ";
	cout << endl;
	
	make_heap(ivec.begin(),ivec.end());
	
	//9 5 8 3 4 0 2 3 1
	for(int i=0;i<ivec.size();i++)
		cout << ivec.at(i) << " ";
	cout << endl;
	
	ivec.push_back(7);
	//9 5 8 3 4 0 2 3 1 7 
	for(int i=0;i<ivec.size();i++)
		cout << ivec.at(i) << " ";
	cout << endl;
	
	push_heap(ivec.begin(),ivec.end());
	//9 7 8 3 5 0 2 3 1 4
	for(int i=0;i<ivec.size();i++)
		cout << ivec.at(i) << " ";
	cout << endl;
	
	pop_heap(ivec.begin(),ivec.end());
	//8 7 4 3 5 0 2 3 1 9 - 9被移到最后，但是没有移除 
	for(int i=0;i<ivec.size();i++)
		cout << ivec.at(i) << " ";
	cout << endl;
	
	ivec.pop_back();//移除9
	//8 7 4 3 5 0 2 3 1  
	for(int i=0;i<ivec.size();i++)
		cout << ivec.at(i) << " ";
	cout << endl;
	
	//排序 
	sort_heap(ivec.begin(),ivec.end());
	
	//0 1 2 3 3 4 5 7 8
	for(int i=0;i<ivec.size();i++)
		cout << ivec.at(i) << " ";
	cout << endl;
	
	int ia[9] = {0,1,2,3,4,8,9,3,5};
	make_heap(ia, ia+9);

	//array 无法动态改变大小，因此不可以对满载的array进行push_heap()操作
	//即使执行，因为无法添加元素，所以会把最后一个元素视为新元素，所以heap不会有任何变化
	sort_heap(ia, ia+9);
	
	//0 1 2 3 3 4 5 8 9
	for(int i=0;i<ivec.size();i++)
		cout << ia[i] << " ";
	cout << endl;

	//再变成heap
	make_heap(ia, ia+9);

	pop_heap(ia, ia+9);

	//9
	cout << ia[8] << endl;


	int ib[6] = {4,1,7,6,2,5};
	make_heap(ib, ib+6);
	for(int i=0; i<6; ++i)
	{
		cout << ib[i] << " ";
	}
	cout << endl;
}

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

//底层以Vector完成的Heap

int ia[9] = {0,1,2,3,4,8,9,3,5};

vector<int> ivec(ia,ia+9);

//0 1 2 3 4 8 9 3 5

for(int i=0;i<ivec.size();i++)

cout << ivec.at(i) << " ";

cout << endl;

make_heap(ivec.begin(),ivec.end());

//9 5 8 3 4 0 2 3 1

for(int i=0;i<ivec.size();i++)

cout << ivec.at(i) << " ";

cout << endl;

ivec.push_back(7);

//9 5 8 3 4 0 2 3 1 7

for(int i=0;i<ivec.size();i++)

cout << ivec.at(i) << " ";

cout << endl;

push_heap(ivec.begin(),ivec.end());

//9 7 8 3 5 0 2 3 1 4

for(int i=0;i<ivec.size();i++)

cout << ivec.at(i) << " ";

cout << endl;

pop_heap(ivec.begin(),ivec.end());

//8 7 4 3 5 0 2 3 1 9 - 9被移到最后，但是没有移除

for(int i=0;i<ivec.size();i++)

cout << ivec.at(i) << " ";

cout << endl;

ivec.pop_back();//移除9

//8 7 4 3 5 0 2 3 1

for(int i=0;i<ivec.size();i++)

cout << ivec.at(i) << " ";

cout << endl;

//排序

sort_heap(ivec.begin(),ivec.end());

//0 1 2 3 3 4 5 7 8

for(int i=0;i<ivec.size();i++)

cout << ivec.at(i) << " ";

cout << endl;

int ia[9] = {0,1,2,3,4,8,9,3,5};

make_heap(ia, ia+9);

//array 无法动态改变大小，因此不可以对满载的array进行push_heap()操作

//即使执行，因为无法添加元素，所以会把最后一个元素视为新元素，所以heap不会有任何变化

sort_heap(ia, ia+9);

//0 1 2 3 3 4 5 8 9

for(int i=0;i<ivec.size();i++)

cout << ia[i] << " ";

cout << endl;

//再变成heap

make_heap(ia, ia+9);

pop_heap(ia, ia+9);

//9

cout << ia[8] << endl;

int ib[6] = {4,1,7,6,2,5};

make_heap(ib, ib+6);

for(int i=0; i<6; ++i)

{

cout << ib[i] << " ";

}

cout << endl;

}

好，Heap的讲解就到这里。

【STL】Heap

Tagged on: STL