番外2 優先隊列預設是大根堆？

stl中預設堆為大根堆，大根堆的定義為：

priority_queue<int> q;
           

根據源碼中的定義，有如下代碼：

template <class _Tp, class _Container = vector<_Tp>,
          class _Compare = less<typename _Container::value_type> >
class _LIBCPP_TEMPLATE_VIS priority_queue
{
public:
    typedef _Container                               container_type;
    typedef _Compare                                 value_compare;
    typedef typename container_type::value_type      value_type;
    typedef typename container_type::reference       reference;
    typedef typename container_type::size_type       size_type;

protected:
    container_type c;
    value_compare comp;
}
           

從最開頭我們可以看出，聲明優先隊列時，第一參數為類型，第二參數為容器，第三參數為比較函數（預設小于）。

那麼問題來了，為什麼預設的這個cmp仿函數為小于的堆，是個大根堆（堆頂元素為最大值）？

建堆時都是一步步push()的，檢視源碼，可以看到如下函數：

// 類裡邊的聲明
void push(value_type&& __v);
// push實作
template <class _Tp, class _Container, class _Compare>
inline
void
priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
{
    c.push_back(_VSTD::move(__v));
    _VSTD::push_heap(c.begin(), c.end(), comp);
}
           

從上述代碼可以看出，優先隊列的push操作就是往容器内push_back一個數，然後執行一個push_heap()操作。

檢視push_heap()操作，可以看到如下代碼：

template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
    __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
}
           

其又掉用了__sift_up()函數，學過堆的小夥伴應該對這個up操作十分熟悉吧！

__sift_up()函數實作如下：

template <class _Compare, class _RandomAccessIterator>
void
__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
          typename iterator_traits<_RandomAccessIterator>::difference_type __len)
{
    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
    if (__len > 1)
    {
        // ((__len - 1) -1) / 2;
        __len = (__len - 2) / 2;
        _RandomAccessIterator __ptr = __first + __len;
        if (__comp(*__ptr, *--__last))
        {
            value_type __t(_VSTD::move(*__last));
            do
            {
                *__last = _VSTD::move(*__ptr);
                __last = __ptr;
                if (__len == 0)
                    break;
                __len = (__len - 1) / 2;
                __ptr = __first + __len;
            } while (__comp(*__ptr, __t));
            *__last = _VSTD::move(__t);
        }
    }
}

template <class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
typename remove_reference<_Tp>::type&&
move(_Tp&& __t) _NOEXCEPT
{
    typedef _LIBCPP_NODEBUG_TYPE typename remove_reference<_Tp>::type _Up;
    return static_cast<_Up&&>(__t);
}
           

從__sift_up()函數的代碼我們可以看出：這個cmp仿函數時一直傳進來了的，而且是根據

__comp(*__ptr, __t)一直在執行某操作的。

這裡就要涉及到heap的up操作了。

heap的up，簡而言之，就是把元素和他的父親節點（/2便是父親節點，完全二叉樹性質）比較，如果符合某性質，就将該節點上移。

以上源碼類似于如下代碼：

void sift-up ( MaxHeap H)
{
    i = H->size;
    item = H->Element [i];
    for ( ; H -> Element [ i/2 ] < item; i /= 2 ) // 與父結點做比較，i / 2 表示的就是父結點的下标
    {
            H -> Element [ i ] = H -> Element [ i/2 ]; // 向下過濾結點
    }
    H -> Element [ i ] = item ; //若for循環完成後,i更新為父節點i，然後将 item 插入
}
           

對于less的話，就是滿足小于，則将節點上移，這樣就形成了一個大根堆。

是以大小根堆可以以以下方式聲明。

// 大根堆   
priority_queue<int, vector<int>, less<int>> q;
// 小根堆   
priority_queue<int, vector<int>, greater<int>> q;