学步园

/*
stl_heap.h 
@功能，Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
这个比较费时间弄懂，先放着。——慢慢看吧。有两种版本一种是最大堆，一种是自定
义比较的。
参看《算法导论V2cn》第6章 堆，书中图画的蛮详细的，但是看这里的代码的时候，搞得
稀里糊涂的。将就着看吧。
堆是为优先队列服务的。
日期，2012年11月1日 星期四
博客，http://blog.csdn.net/shunqiziranhao007/article/details/8138269
环境，win7-32-vs2010
*/
/* NOTE: This is an internal header file, included by other STL headers.
 *   You should not attempt to use it directly.
 */

#ifndef __SGI_STL_INTERNAL_HEAP_H
#define __SGI_STL_INTERNAL_HEAP_H

__STL_BEGIN_NAMESPACE

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1209
#endif

// 这里的堆是最大堆，堆顶为最大值
// 压入堆，调整hole到top间的堆为最大堆
// 参1是辅助，相当于数组头。
template <class _RandomAccessIterator, class _Distance, class _Tp>
void 
__push_heap(_RandomAccessIterator __first,
	_Distance __holeIndex, _Distance __topIndex, _Tp __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;
}

// 堆顶索引为0
template <class _RandomAccessIterator, class _Distance, class _Tp>
inline void 
__push_heap_aux(_RandomAccessIterator __first,
	_RandomAccessIterator __last, _Distance*, _Tp*)
{
	__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
		_Tp(*(__last - 1)));
}

template <class _RandomAccessIterator>
inline void 
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
		_LessThanComparable);
	__push_heap_aux(__first, __last,
		__DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Distance, class _Tp, 
class _Compare>
void
__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
	_Distance __topIndex, _Tp __value, _Compare __comp)
{
	_Distance __parent = (__holeIndex - 1) / 2;
	while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
		*(__first + __holeIndex) = *(__first + __parent);
		__holeIndex = __parent;
		__parent = (__holeIndex - 1) / 2;
	}
	*(__first + __holeIndex) = __value;
}

template <class _RandomAccessIterator, class _Compare,
class _Distance, class _Tp>
inline void 
__push_heap_aux(_RandomAccessIterator __first,
	_RandomAccessIterator __last, _Compare __comp,
	_Distance*, _Tp*) 
{
	__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
		_Tp(*(__last - 1)), __comp);
}

template <class _RandomAccessIterator, class _Compare>
inline void 
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	_Compare __comp)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	__push_heap_aux(__first, __last, __comp,
		__DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
}

// 参1，范围头，参2，调整开始，参3，范围长度，参4，调整的值
// 调整堆，调整为以参2为堆顶的最大堆
template <class _RandomAccessIterator, class _Distance, class _Tp>
void 
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
	_Distance __len, _Tp __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);
}

// 参1，范围开始，参2，范围结束，参3，,结果位置，参4，值，参5，距离类型
// 获取堆顶元素的值，然后重新调整堆为最大堆
template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void 
	__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	_RandomAccessIterator __result, _Tp __value, _Distance*)
{
	*__result = *__first;
	// 继续调整堆
	__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
}

template <class _RandomAccessIterator, class _Tp>
inline void 
	__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
	_Tp*)
{
	// 范围减小了1,将弹出的值放在最后一个元素的位置中，注意last是最后一个元素的
	// 下一个位置，不是最后一个元素的位置
	__pop_heap(__first, __last - 1, __last - 1, 
		_Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
}

// 弹出范围内的堆顶元素
template <class _RandomAccessIterator>
inline void pop_heap(_RandomAccessIterator __first, 
	_RandomAccessIterator __last)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
		_LessThanComparable);
	__pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Distance,
class _Tp, class _Compare>
	void
	__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
	_Distance __len, _Tp __value, _Compare __comp)
{
	_Distance __topIndex = __holeIndex;
	_Distance __secondChild = 2 * __holeIndex + 2;
	while (__secondChild < __len) {
		if (__comp(*(__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, __comp);
}

template <class _RandomAccessIterator, class _Tp, class _Compare, 
class _Distance>
	inline void 
	__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	_RandomAccessIterator __result, _Tp __value, _Compare __comp,
	_Distance*)
{
	*__result = *__first;
	__adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
	__value, __comp);
}

template <class _RandomAccessIterator, class _Tp, class _Compare>
inline void 
	__pop_heap_aux(_RandomAccessIterator __first,
	_RandomAccessIterator __last, _Tp*, _Compare __comp)
{
	__pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
		__DISTANCE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Compare>
inline void 
	pop_heap(_RandomAccessIterator __first,
	_RandomAccessIterator __last, _Compare __comp)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	__pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
}

template <class _RandomAccessIterator, class _Tp, class _Distance>
void 
	__make_heap(_RandomAccessIterator __first,
	_RandomAccessIterator __last, _Tp*, _Distance*)
{
	if (__last - __first < 2) return;
	_Distance __len = __last - __first;
	_Distance __parent = (__len - 2)/2;

	// 从中间开始调整堆
	while (true) {
		__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
		if (__parent == 0) return;
		// 一个一个的调整
		__parent--;
	}
}

// 给个范围建个最大堆
template <class _RandomAccessIterator>
inline void 
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
		_LessThanComparable);
	__make_heap(__first, __last,
		__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}

// 自定义compare的
template <class _RandomAccessIterator, class _Compare,
class _Tp, class _Distance>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	_Compare __comp, _Tp*, _Distance*)
{
	if (__last - __first < 2) return;
	_Distance __len = __last - __first;
	_Distance __parent = (__len - 2)/2;

	while (true) {
		__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
			__comp);
		if (__parent == 0) return;
		__parent--;
	}
}

// 自定义compare的
template <class _RandomAccessIterator, class _Compare>
inline void 
make_heap(_RandomAccessIterator __first, 
	_RandomAccessIterator __last, _Compare __comp)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	__make_heap(__first, __last, __comp,
		__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}

// 堆排序
template <class _RandomAccessIterator>
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
		_LessThanComparable);
	while (__last - __first > 1)
		pop_heap(__first, __last--);
}

template <class _RandomAccessIterator, class _Compare>
void 
sort_heap(_RandomAccessIterator __first,
	_RandomAccessIterator __last, _Compare __comp)
{
	__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
	while (__last - __first > 1)
		pop_heap(__first, __last--, __comp);
}

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1209
#endif

__STL_END_NAMESPACE

#endif /* __SGI_STL_INTERNAL_HEAP_H */

// Local Variables:
// mode:C++
// End: