- heap不属于STL容器的组件，属于幕后角色，是priority_queue的助手
- priority_queue 允许用户以任何次序将任何元素推入容器内，但是取出的时候需要从优先级最高(也就是数值最高)的元素开始取，这种思想是基于heap的函数实现
- 如果使用list作为 priority_queue 的底层实现机制，元素的插入 *** 作可以使用常数的时间，但是不好找 极值，需要进行线性扫描和遍历；如果考虑到大小这个关键因素，进行元素的排序，随后进行元素之间的衔接，降低了元素的插入效率
- 使用binary search tree作为priority的底层机制，这样对于元素的插入和取极值就有O(logN)的表现；但是缺点是：1，binary search tree需要具备足够的随机性；2，binary search tree实现很难；
- binary heap是一种 complate binary tree(完全二叉树)，除了最底层叶节点之外都是处于饱和的状态，而最底层的叶节点从左只有不得有空隙，示例如下
- complate binary tree(完全二叉树)整棵树内部没有任何的节点漏洞
- 好处：1，使用array存储所有的节点，保留#0 元素的位置 (将其设为无限大或者无限小),那么当 complate binary tree(完全二叉树)的某个节点位于array数组中的i处的时候，其左子树节点必然位于array的 2i 处，其右子树的节点必然位于array的 2*i+1 的位置。 ( 这里的 / 表示取整数)，通过保留#0 的 *** 作，可以使用array
- 轻而易举实现出complate binary tree。使用数组的方式表达完全二叉树的方式 称为隐式 表述法
- 考虑到array无法动态的改变大小，使用vector代替array实现 完全二叉树
- 根据元素的排列方式 heap分为max-heap和min-heap，前者每个节点的键值 都大于或者等于其子节点的键值 ；后者 每个节点的键值都小于或者等于其每个子节点的键值
- max-heap 最大值在根节点，其总是位于底层的array或者vector的开头；
- min-heap 最小值在根节点，其总是位于底层的array或者vector的开头；
- STL 供应的是 max-heap 本文所有的heap都按照 max-heap处理
- 新加入的元素一定是放在最下一层作为叶节点，并填补从左到右的第一个空格，也就是底层vector()的end()处
- 执行上溯程序，将新节点和父接地那记性比较，如果大于父节点，就进行父子对换，如此一直上溯，直到不需要对换或者直到遇到根节点为止
- 接收两个迭代器表示heap的底部 *** 作(vector)的头尾，并且新的元素插入到底部容器的最尾端，如果不符合这两个条件，那么push_heap的结果是不可预期的
- distance_type 方便的决定某个迭代器的类型 参考链接如下
- STL源码剖析 5中迭代器型别_CHYabc123456hh的博客-CSDN博客
templatepop_heap() 算法inline void push_heap(RandomAccessIterator first,RandomAccessIterator last){ //函数被调用的时候 新元素应已经置于底部容器的最尾端 //distance_type 用于判断迭代器的类型，从而判定是否进行偏特化 *** 作 __push_heap_aux(first,last,distance_type(first),value_type(first)); } template inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance *,T*){ //根据implicit representation heap的结构特性，新值必须置于底部容器的最尾端，即第一个洞号(last-first)-1 __push_heap(first,Distance((last-first)-1),Distance(0),T(*(last-1))); } //以下这组push_back() 不允许指定 "大小比较的标准" template void __push_heap(RandomAccessIterator first,Distance holeIndex, Distance topIndex,T value){ Distance parent = (holeIndex - 1)/2; //找出父节点 //当holeIndex并没有到达顶峰的同时 父节点还小于新值 （不符合heap的次序特性） //使用operator < 进行元素的比较，因此STL heap是一种max-heap //父节点是动态变化的 //每次是和value进行比较，因此不需要进行父子元素值的对调，直接让子元素接管父亲的数值 while(holeIndex > topIndex && *(first + parent) < value){ *(first + holeIndex) = *(first + parent); //令洞值为父值,也就是孩子赋予了父亲的数值，父亲位置 holeIndex = parent; //调整洞号，向上提升至父节点 parent = (holeIndex - 1)/2;//新洞的父节点 }//持续至顶端，或者满足 heap的次序特性为止 *(first + holeIndex) = value;//令新洞为新的数值，完成插入操作 }
- d出最大元素，根节点缺失需要使用最末尾的元素进行弥补，然后执行下放程序，将根节点的数值和最大的叶子节点进行互换，以此类推，直到这个洞的键值大于左右两个子节点，或者下放至叶子节点为止
- pop_heap代码
//这个堆没有指定 大小比较的标准 templateinline void __pop_heap(RandomAccessIterator first,RandomAccessIterator last, RandomAccessIterator result,T value,Distance *){ *result = *first; //设定尾值为首值，也就是此刻的尾值为先前的根节点 //可以通过底层容器的 pop_back()取出尾值 //重新调整 heap 洞号为0(即树根处)，将其数值设定为 value(先前的尾节点的数值) __adjust_heap(first,Distance(0),Distance(last-first),value); } //这个堆没有指定 大小比较的标准 template void __adjust_heap(RandomAccessIterator first,Distance holeIndex, Distance len,T value){ Distance topIndex = holeIndex; Distance secondChild = 2 * holeIndex +2;//洞节点的右子节点 while(secondChild < len){ //比较洞节点的左右两个孩子的数值，然后以secondChild代表较大的子节点 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; } *(first + holeIndex) = value; }
- pop_heap之后，最大元素将被放置于底部容器的最尾端，并没有被取走。可以使用底部容器提供的back()函数获取这个数值，也可以使用vector提供的pop_back()函数将其移除
- pop_heap可以获得heap中键值最大的元素，持续使用pop_heap,不断得到最大的元素，就可以实现排序。需要注意的是每没用一次pop_heap都需要将 *** 作范围从后向前缩减一个元素。
- sort_heap()函数接收两个迭代器，用来表现一个heap底部容器的头尾。如果不符合这个条件，sort_heap的排序结果未可预期。
- *排序过后的heap已经被破坏，不再是一个合法的堆了，相当于 *** 作底层的元素，修改了元素，破坏性是无法修改的
templatevoid sort_heap(RandomAccessIterator first,RandomAccessIterator last){ //每执行一次pop_heap(),极值(在STL heap中为极大值)就会被放在尾端 //扣除尾端再次执行pop_heap()，次极值又被放在新的尾端，按照上述流程一直执行，最后得到排序结果 while (last - first > 1){ std::pop_heap(first,last--);//每次执行pop_heap()一次， *** 作范围即缩减一格 } }
make_heap()
- 这个函数的目的是为了将一段现有的数据将其转化为堆的形式，主要依据就是complate binary tree 的隐式表述
templateheap没有迭代器void __make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance *){ if (last - first < 2){ //如果长度为0或者为1，不需要重新排列 return; } Distance len = last - first; //找出第一个需要重新排列的子树的头部，以parent标定 //考虑到任何节点不需要执行perlocate down，因此使用hole Index进行命名更好 Distance parent = (len - 2)/2; while (true){ //重新排列以parent为首的子树 //len的目的是为了让__adjust_heap() 判断操作的范围 __adjust_heap(first,parent,len,T(*(first + parent))); if (parent == 0){ return; //走完根节点 结束 } parent--; // (即将重拍子树的)头部向前一个节点 } }
- heap不提供遍历的功能，也不提供迭代器
int main(){
int ia[9] = {0,1,2,3,4,8,9,3,5};
std::vector i_vec(ia,ia+9);
std::make_heap(i_vec.begin(),i_vec.end());
for (int i = 0; i < i_vec.size(); ++i) {
std::cout << i_vec[i] << ' '; //9 5 8 3 4 0 2 3 1
}
std::cout << std::endl;
i_vec.push_back(7);
std::push_heap(i_vec.begin(),i_vec.end());
for (int i = 0; i < i_vec.size(); ++i) {
std::cout << i_vec[i] << ' '; //9 7 8 3 5 0 2 3 1 4
}
std::cout << std::endl;
std::pop_heap(i_vec.begin(),i_vec.end());
std::cout << i_vec.back() << std::endl; //9 return but no remove
i_vec.pop_back(); //remove last elem and no return
for (int i = 0; i < i_vec.size(); ++i) {
std::cout << i_vec[i] << ' '; //8 7 4 3 5 0 2 3 1
}
std::cout << std::endl;
std::sort_heap(i_vec.begin(),i_vec.end());
for (int i = 0; i < i_vec.size(); ++i) {
std::cout << i_vec[i] << ' '; //0 1 2 3 3 4 5 7 8
}
std::cout << std::endl;
{
//test heap (底层使用array实现)
int ia[9] = {0,1,2,3,4,8,9,3,5};
std::make_heap(ia,ia+9);
//array不能动态的改变大小，因此不可以对满载的array进行push_heap()操作
//需要先在array的尾端增加一个元素
std::sort_heap(ia,ia+9);
for (int i = 0; i < 9; ++i) {
std::cout << ia[i] << ' '; //0 1 2 3 3 4 5 8 9
}
std::cout << std::endl;
//经过排序之后的heap 不再是一个合法的heap
//重新再做一个heap
std::make_heap(ia,ia+9);
std::pop_heap(ia,ia+9);
std::cout << ia[8] << std::endl; //8
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）