priority_queue

因为底层比较简单（置于vector的最大堆/最小堆），所以放到前面来分析

1
2
3
4
5
6
7
8
9
template<typename _Tp, typename _Sequence = vector<_Tp>,
    typename _Compare  = less<typename _Sequence::value_type> >
class priority_queue
{
    ...
    protected:
      _Sequence  c;  //底层容器
      _Compare   comp; //元素大小标准
}

Constructors

指定初值。such as:int a[4] = {1,2,3,4}; priority_queue q(a,a+4);

首先是vector的初始化，将初值先放入了vector中。

之后进入

1
2
3
4
5
6
7
8
9
10
    template<typename _InputIterator>
    priority_queue(_InputIterator __first, _InputIterator __last,
            const _Compare& __x = _Compare(),
            _Sequence&& __s = _Sequence())
: c(std::move(__s)), comp(__x)
    {
    __glibcxx_requires_valid_range(__first, __last);
    c.insert(c.end(), __first, __last);
    std::make_heap(c.begin(), c.end(), comp);
}

初始化底层容器c，并将之前存入vector的初值插入c，之后调用make_heap创建堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<typename _RandomAccessIterator, typename _Compare>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    _Compare __comp)
{
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    _DistanceType;

    if (__last - __first < 2)
        return;

    const _DistanceType __len = __last - __first;
    _DistanceType __parent = (__len - 2) / 2;  //最后一个子节点的父节点
    while (true)
{
    _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
    std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                __comp);
    if (__parent == 0)
    return;
    __parent--;
}
}

从最后一个子树的父节点开始调用__adjust_heap将子树调整为最大堆（最小堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template<typename _RandomAccessIterator, typename _Distance,
    typename _Tp, typename _Compare>

/*
args:基准指针为__first，洞号为__holeIndex，长度为__len，洞号处的值调整为__value，大小比较为__comp
这样写的好处是可以直接复用，正常使用时，设置__value = *(__first + __holeIndex)即可
当需要弹出顶端元素时，设置__value = *(__first + __last -1)即可
*/
void
__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--;                                  //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));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
    typename _Compare>
void
__push_heap(_RandomAccessIterator __first,
    _Distance __holeIndex, _Distance __topIndex, _Tp __value,
    _Compare __comp)
{
    _Distance __parent = (__holeIndex - 1) / 2;     //当前__holeIndex的父节点
    
    //当尚未到达顶端且父节点小于__value
    while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
{
    *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
    __holeIndex = __parent;
    __parent = (__holeIndex - 1) / 2;
}
    *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
}

push && pop

  1. push就是先将元素推入底层vector末端，之后调用push_heap重排
    1
    2
    3
    4
    5
    6
    void
    push(value_type&& __x)
    {
    c.push_back(std::move(__x));
    std::push_heap(c.begin(), c.end(), comp);
    }
1
2
3
4
5
6
7
8
9
10
11
template<typename _RandomAccessIterator, typename _Compare>
inline void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _Compare __comp)
{
    ...
    _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
    std::__push_heap(__first, _DistanceType((__last - __first) - 1),
            _DistanceType(0), _GLIBCXX_MOVE(__value),
            __gnu_cxx::__ops::__iter_comp_val(__comp));
}
  1. pop也是调用pop_heap进行重排，再以底层的vector的pop_back将其弹出
    1
    2
    3
    4
    5
    6
    7
    void
    pop()
    {
    __glibcxx_requires_nonempty();
    std::pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
    }

可以看到pop_heap是将最后一个元素的值存入value中，将第一位设置为__holeIndex之后对前len-1位进行堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename _RandomAccessIterator, typename _Compare>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _RandomAccessIterator __result, _Compare __comp)
{
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;

    _ValueType __value = _GLIBCXX_MOVE(*__result);
    *__result = _GLIBCXX_MOVE(*__first);
    std::__adjust_heap(__first, _DistanceType(0),
            _DistanceType(__last - __first),
            _GLIBCXX_MOVE(__value), __comp);
}