STL 源码剖析算法 stl_heap.h

首页 > 代码库 > STL 源码剖析算法 stl_heap.h

STL 源码剖析算法 stl_heap.h

2024-07-13 04:45:53 226人阅读

本文为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:

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > STL 源码剖析 算法 stl_heap.h

STL 源码剖析 算法 stl_heap.h

看完仍有疑问？有类似问题直接问程序猿

首页 > 代码库 > STL 源码剖析算法 stl_heap.h

STL 源码剖析算法 stl_heap.h