STL 源代码分析算法 stl

本文senlie原版的。转载请保留此地址：http://blog.csdn.net/zhengsenlie

heap

-------------------------------------------------------------------------

binary heap 是一种全然二叉树。

隐式表示法：以 array 表述 tree。

小技巧：将 array 的 #0 元素保留。则第 i 个元素的左右子节点各自是 2i 和 2i + 1，

父节点是i/2 --> STL 里没有採用这样的小技巧

将 array 无法动态改变大小，所以用 vector 替代 array

这个文件中提供了各种堆操作的算法，注意没有 heap 类

图 4-20

演示样例：

#include <vector>

#include <iostream>

#include <iterator>

#include <algorithm>

using namespace std;

void display(const vector<int> &v){

	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

	cout << endl;

}

int main(){

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

	vector<int> ivec(ia, ia + sizeof(ia)/sizeof(int));

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

	display(ivec);

	ivec.push_back(7);

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

	display(ivec);

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

	ivec.pop_back();

	display(ivec);

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

	display(ivec);

}

源代码：

#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

template <class RandomAccessIterator, class Distance, class T>

void __push_heap(RandomAccessIterator first, Distance holeIndex,

                 Distance topIndex, T value) {

  Distance parent = (holeIndex - 1) / 2;  //找到父节点

  // 当尚未到达顶端。且父节点小于新值(于是不符合 heap 的次序特性)

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

    *(first + holeIndex) = *(first + parent); //令洞值为父值

    holeIndex = parent; //调整洞号。向上提升至父节点

    parent = (holeIndex - 1) / 2; //新洞的父节点

  }

  *(first + holeIndex) = value; //令洞值为新值。完毕插入操作

}

template <class RandomAccessIterator, class Distance, class T>

inline void __push_heap_aux(RandomAccessIterator first,

                            RandomAccessIterator last, Distance*, T*) {

  __push_heap(first, Distance((last - first) - 1), Distance(0),

              T(*(last - 1)));

}

/*调用此函数时，新元素应已置于底部容器的最尾端

--> 什么时候置的？

--> stl_heap 不正确外开放，仅仅在 STL 内部使用，使用 push_heap 的其它 STL 程序应该注意在调用

push_heap 函数前，将新元素置于 heap 底部容器的最尾端

*/

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, class Compare>

void __push_heap(RandomAccessIterator first, Distance holeIndex,

                 Distance topIndex, T 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;

}

//STL 里非常多这样的函数体里直接调用还有一个函数的函数。感觉这样不太好。添加了堆栈的开销，

//为什么不直接就调用里面那个函数呢

template <class RandomAccessIterator, class Compare, class Distance, class T>

inline void __push_heap_aux(RandomAccessIterator first,

                            RandomAccessIterator last, Compare comp,

                            Distance*, T*) {

  __push_heap(first, Distance((last - first) - 1), Distance(0),

              T(*(last - 1)), comp);

}

template <class RandomAccessIterator, class Compare>

inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,

                      Compare comp) {

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

}

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, class T, class Distance>

inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,

                       RandomAccessIterator result, T value, Distance*) {

  *result = *first;

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

}

template <class RandomAccessIterator, class T>

inline void __pop_heap_aux(RandomAccessIterator first,

                           RandomAccessIterator last, T*) {

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

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

}

template <class RandomAccessIterator>

inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {

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

}

template <class RandomAccessIterator, class Distance, class T, class Compare>

void __adjust_heap(RandomAccessIterator first, Distance holeIndex,

                   Distance len, T 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 T, class Compare, class Distance>

inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,

                       RandomAccessIterator result, T value, Compare comp,

                       Distance*) {

  //将首值(即要 pop 出来的值)存放在 result 所指处。

  *result = *first;

  //又一次调整 heap 。 洞号为0。欲调整值为 value

  __adjust_heap(first, Distance(0), Distance(last - first), value, comp);

}

template <class RandomAccessIterator, class T, class Compare>

inline void __pop_heap_aux(RandomAccessIterator first,

                           RandomAccessIterator last, T*, Compare comp) {

  __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,

             distance_type(first));

}

template <class RandomAccessIterator, class Compare>

inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,

                     Compare comp) {

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

}

template <class RandomAccessIterator, class T, class Distance>

void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,

                 Distance*) {

  if (last - first < 2) return;

  Distance len = last - first;

  Distance parent = (len - 2)/2;

  while (true) {

    __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 Compare, class T, class Distance>

void __make_heap(RandomAccessIterator first, RandomAccessIterator last,

                 Compare comp, T*, Distance*) {

  if (last - first < 2) return;

  Distance len = last - first;

  //找出第一个须要重排的子树的头部。以 parent 标示出。

Distance parent = (len - 2)/2;

  while (true) {

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

    if (parent == 0) return; //走完根节点。就结束了。

    parent--; //实际上就是沿着第一个父节点从左到右调整值使父节点的值大于(或小于)两个子节点

  }

}

template <class RandomAccessIterator, class Compare>

inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,

                      Compare comp) {

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

}

template <class RandomAccessIterator>

void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {

  //每次运行一次 pop_heap() ，极值被放在尾端

  //扣除尾端再运行一次 pop_heap()。次极值又被放在新尾端

  //一直这样下去，最后就可以得到排序结果

  while (last - first > 1) pop_heap(first, last--);

}

template <class RandomAccessIterator, class Compare>

void sort_heap(RandomAccessIterator first, RandomAccessIterator last,

               Compare comp) {

  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:

巴特西

STL 源代码分析算法 stl_heap.h

最新文章

热门文章

巴特西

STL 源代码分析 算法 stl_heap.h

最新文章

热门文章

STL 源代码分析算法 stl_heap.h