首页 > 编程语言 >pop_heap 源码剖析

pop_heap 源码剖析

时间:2022-12-06 19:35:44浏览次数:44  
标签:Last Pred pop 源码 heap Hole First


一:用法示例

一共两个重载:

default (1)   
template <class RandomAccessIterator>
  void pop_heap ( RandomAccessIterator first ,  RandomAccessIterator last ) ;
custom (2)   
template <class RandomAccessIterator, class Compare>
  void pop_heap (RandomAccessIterator first ,  RandomAccessIterator last  , Compare comp ) ;

作用范围是[ first , last ),使用pop_heap前必须保证在该作用范围的数满足(大顶或小顶)堆。

该函数的作用就是把堆顶的元素(也就是数组的第一个元素)放在末尾,原来末尾的元素移到前面,在移动过程,同样的,也要保证[ first , last - 1 )满足(大顶或小顶)堆。

例子:

#include<iostream>
#include<functional>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{

int a[10] = { 2,1,6,4,9,10,3,5,8,7 };
vector<int> v(a, a + 10);
sort(v.begin(), v.end());//现在是一个小顶堆

pop_heap(v.begin(), v.end(), greater<>());//现在1已经到了数组末尾

for (auto it = v.begin(); it != v.end(); it++)
cout << *it << " ";//2 4 3 8 5 6 7 10 9 1
cout << endl;

return 0;
}


二:源码及剖析

记住源码阅读顺序是从最后一个往前读,该函数用到了push_heap源代码的知识,链接为: ​​push_heap​​   ,建议读者对照着看。

// TEMPLATE FUNCTION pop_heap WITH PRED
template<class _RanIt,
class _Diff,
class _Ty,
class _Pr> inline
void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom,
_Ty&& _Val, _Pr _Pred)
{ // percolate _Hole to _Bottom, then push _Val, using _Pred
/*
_Hole为0,表示起点位置
_Bottom为begin()-end()-1,也就是数组长度减一
_Val保存着最后位置的值,也就是*(end()-1)
*/
_Diff _Top = _Hole;//_Top等于0
_Diff _Idx = 2 * _Hole + 2;//转到_Hole的右孩子处

for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
{ // move _Hole down to larger child
if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1))))
--_Idx;//_Idx指向左右孩子值较大(小)的位置
*(_First + _Hole) = _STD move(*(_First + _Idx));
_Hole = _Idx;
}

if (_Idx == _Bottom)
{ // only child at bottom, move _Hole down to it
*(_First + _Hole) = _STD move(*(_First + (_Bottom - 1)));
_Hole = _Bottom - 1;
}
_Push_heap(_First, _Hole, _Top, _STD move(_Val), _Pred);
}

template<class _RanIt,
class _Diff,
class _Ty,
class _Pr> inline
void _Pop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
_Ty&& _Val, _Pr _Pred, _Diff *)
{ // pop *_First to *_Dest and reheap, using _Pred
*_Dest = _STD move(*_First);//把第一个元素赋给最后一个,最后一个位置的值早已经保存在_Val
_Adjust_heap(_First, _Diff(0), _Diff(_Last - _First),
_STD move(_Val), _Pred);
}

template<class _RanIt,
class _Ty,
class _Pr> inline
void _Pop_heap_0(_RanIt _First, _RanIt _Last, _Pr _Pred, _Ty *)
{ // pop *_First to *(_Last - 1) and reheap, using _Pred
_Ty _Val = _STD move(*(_Last - 1));
_Pop_heap(_First, _Last - 1, _Last - 1,
_STD move(_Val), _Pred, _Dist_type(_First));
}

template<class _RanIt,
class _Pr> inline
void _Pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
{ // pop *_First to *(_Last - 1) and reheap, using _Pred
_Pop_heap_0(_Unchecked(_First), _Unchecked(_Last), _Pred,
_Val_type(_First));
}

template<class _RanIt,
class _Pr> inline
void pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
{ // pop *_First to *(_Last - 1) and reheap, using _Pred
_DEBUG_RANGE_PTR(_First, _Last, _Pred);
_DEBUG_HEAP_PRED(_First, _Last, _Pred);
if (2 <= _Last - _First)
_Pop_heap(_Unchecked(_First), _Unchecked(_Last), _Pred);
}

// TEMPLATE FUNCTION pop_heap
template<class _RanIt> inline
void pop_heap(_RanIt _First, _RanIt _Last)
{ // pop *_First to *(_Last - 1) and reheap, using operator<
_STD pop_heap(_First, _Last, less<>());
}




源码摘抄自Visual Studio 2015安装目录algorithm文件中。



点击进入目录----> ​​ C++源码剖析目录​​











标签:Last,Pred,pop,源码,heap,Hole,First
From: https://blog.51cto.com/u_11937443/5916554

相关文章