STL 더미 실현

머리말
더 미 는 매우 중요 한 데이터 구조 입 니 다. 우리 가 자주 사용 하 는 우선 대기 열 은 더 미 를 바탕 으로 하 는 데이터 구조 이 고 더 미 를 쌓 는 것 도 더 미 를 바탕 으로 하 는 것 입 니 다. 그래서 우 리 는 더 미 를 실현 하 는 것 을 이해 해 야 합 니 다. 그 전에 자신 이 쌓 은 원리 에 따라 더 미 를 실 현 했 습 니 다. 지금 STL 에 쌓 인 실현 코드 를 분석 해 보 겠 습 니 다. STL 의 더 미 는 자신 이 실현 한 코드 보다 훨씬 많 을 것 입 니 다.하지만 원 리 는 같 습 니 다. 아래 를 살 펴 보 겠 습 니 다.
쌓 인 실현
STL 에 서 는 사람들 이 사용 할 수 있 도록 일련의 코드 를 제공 했다.분석 해 보 자.우 리 는 쌓 인 저장 형식 이 배열 을 이용 하여 이 루어 진 다 는 것 을 알 고 있다. 그러면 배열 의 서열 을 정 하고 쌓 인 것 인지 아 닌 지 어떻게 판단 합 니까?다음은 쌓 인 실현 코드 인지 아 닌 지 를 판단 하 는 원 리 는 매우 간단 하 다. 즉, 쌓 인 성질 을 만족 시 키 는 지, 부모 노드 는 자식 노드 (최대 쌓 기) 보다 크다.물론 여기 is_heap 에는 다른 과부하 형식 이 있 으 며, 여 기 는 더 이상 열거 하지 않 습 니 다.

  /**
   *  @brief  Determines whether a range is a heap using comparison functor.
   *  @param  __first  Start of range.
   *  @param  __last   End of range.
   *  @param  __comp   Comparison functor to use.
   *  @return  True if range is a heap, false otherwise.
   *  @ingroup heap_algorithms
  */
template
inline bool is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { //             
    // concept requirements
    __glibcxx_function_requires(_RandomAccessIteratorConcept<_randomaccessiterator>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    const auto __dist = std::distance(__first, __last);
    typedef __decltype(__comp) _Cmp;
    __gnu_cxx::__ops::_Iter_comp_iter<_cmp> __cmp(_GLIBCXX_MOVE(__comp));
    return std::__is_heap_until(__first, __dist, __cmp) == __dist;
}

template
_Distance __is_heap_until(_RandomAccessIterator __first, _Distance __n, _Compare& __comp) {     
    _Distance __parent = 0;
    for (_Distance __child = 1; __child < __n; ++__child) {     //          ，     ，           （   ）
	    if (__comp(__first + __parent, __first + __child))
	        return __child;
	    if ((__child & 1) == 0)
	        ++__parent;
	}
    return __n;
}

만약 배열 의 서열 을 정 하고 쌓 인 성질 을 만족 시 키 지 못 한다 면 어떻게 그 를 쌓 인 성질 로 바 꿀 수 있 습 니까?여기에 make_heap 실현 이 있 으 니, 우 리 는 그 실현 을 살 펴 보 자.그 실현 원리 도 쌓 인 성질 에 따라 마지막 비 잎 노드 (자식 노드 가 있 는 노드) 를 찾 아 부모 노드 가 자식 노드 보다 큰 것 을 만족 시 키 는 지 확인 하고 만족 하지 않 으 면 부자 노드 의 값 을 교환 하면 뿌리 노드 까지 한다.

  /**
   *  @brief  Construct a heap over a range.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap.
   *  @ingroup heap_algorithms
   *
   *  This operation makes the elements in [__first,__last) into a heap.
  */
template
inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_randomaccessiterator>)
    __glibcxx_function_requires(_LessThanComparableConcept::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);

    __gnu_cxx::__ops::_Iter_less_iter __comp;
    std::__make_heap(__first, __last, __comp);
}

template
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--;
	}
}

template
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--;
	    *(__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;
	}
    __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
	__cmp(_GLIBCXX_MOVE(__comp));
    std::__push_heap(__first, __holeIndex, __topIndex, _GLIBCXX_MOVE(__value), __cmp);
}

template
void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value, _Compare& __comp) {
    _Distance __parent = (__holeIndex - 1) / 2;
    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_heap 하여 더미 의 성질 을 만족 시 킵 니 다.쌓 인 꼬리 에 원 소 를 추가 한 후에 쌓 인 성질 을 파괴 하고 쌓 인 성질 을 만족 시 킬 때 까지 '위로 이동' 을 할 수 있다.

/**
   *  @brief  Push an element onto a heap.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap + element.
   *  @ingroup heap_algorithms
   *
   *  This operation pushes the element at last-1 onto the valid heap
   *  over the range [__first,__last-1).  After completion,
   *  [__first,__last) is a valid heap.
*/
template
inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
    typedef typename iterator_traits<_randomaccessiterator>::value_type _ValueType;
    typedef typename iterator_traits<_randomaccessiterator>::difference_type _DistanceType;

    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_randomaccessiterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<_valuetype>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive(__first, __last);
    __glibcxx_requires_heap(__first, __last - 1);

    __gnu_cxx::__ops::_Iter_less_val __comp;
    _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
    std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
}

내부 용기 의 끝 에 원 소 를 꺼 내 서 쌓 인 성질 을 파괴 한 후 '아래로 이동' 을 실행 하여 쌓 인 성질 을 보증 합 니 다.

  /**
   *  @brief  Pop an element off a heap using comparison functor.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap.
   *  @param  __comp   Comparison functor to use.
   *  @ingroup heap_algorithms
   *
   *  This operation pops the top of the heap.  The elements __first
   *  and __last-1 are swapped and [__first,__last-1) is made into a
   *  heap.  Comparisons are made using comp.
  */
template
inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_randomaccessiterator>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
    __glibcxx_requires_non_empty_range(__first, __last);
    __glibcxx_requires_heap_pred(__first, __last, __comp);

    if (__last - __first > 1) {
	    typedef __decltype(__comp) _Cmp;
	    __gnu_cxx::__ops::_Iter_comp_iter<_cmp> __cmp(_GLIBCXX_MOVE(__comp));
	    --__last;
	    std::__pop_heap(__first, __last, __last, __cmp);
	}
}

template
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);
}

STL 에서 도 정렬 의 실현 을 보 여 주 었 습 니 다. 코드 는 다음 과 같 습 니 다.

 /**
   *  @brief  Sort a heap using comparison functor.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap.
   *  @param  __comp   Comparison functor to use.
   *  @ingroup heap_algorithms
   *
   *  This operation sorts the valid heap in the range [__first,__last).
   *  Comparisons are made using __comp.
  */
template
inline void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_randomaccessiterator>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
    __glibcxx_requires_heap_pred(__first, __last, __comp);

    typedef __decltype(__comp) _Cmp;
    __gnu_cxx::__ops::_Iter_comp_iter<_cmp> __cmp(_GLIBCXX_MOVE(__comp));
    std::__sort_heap(__first, __last, __cmp);
}

template
void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
    while (__last - __first > 1) {
	    --__last;
	    std::__pop_heap(__first, __last, __last, __comp);
	}
}