I am using the std::priority_queue and I'm trying to understand how does the pop function works to know how many compares occurs in every pop call. I have seen that the priority queue is based on the std::heap. Specifically, the pop function is using the __adjust_heap function. I have tried to understand this function but I encountered difficulties with the logic part.
I know that in the standard pop_heap function the top object is removed and then the last one is taken to the top and being compared with its two children. but in this code it seems not to be the case.
can someone help me understand how does it work here?
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __value, _Compare __comp)
{
const _Distance __topIndex = __holeIndex;
_Distance __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
if (__comp(__first + __secondChild,
__first + (__secondChild - 1)))
__secondChild--;
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
__holeIndex = __secondChild;
}
if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
{
__secondChild = 2 * (__secondChild + 1);
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
+ (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
std::__push_heap(__first, __holeIndex, __topIndex,
_GLIBCXX_MOVE(__value),
__gnu_cxx::__ops::__iter_comp_val(__comp));
}
Aucun commentaire:
Enregistrer un commentaire