sort_heap

힙 정렬 된 범위에 변환합니다.

template<class RandomAccessIterator>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
   );
template<class RandomAccessIterator, class Predicate>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last,
      Predicate _Comp
   );

매개 변수

• _First
  대상 힙의 위치를 첫 번째 요소의 주소를 지정 하는 임의 액세스 반복기입니다.

• _Last
  이전 대상 힙의 마지막 요소 위치 주소는 임의 액세스 반복기입니다.

• _Comp
  한 요소가 다른 보다 작은 것이 정의 조건자 함수의 사용자 정의 개체입니다.두 인수를 사용 하 고 반환 하는 이진 술 부 true 만족 스 러 우면 및 거짓 만족 하지 않을 때.

설명

힙 두 가지 속성이 있습니다.

• 첫 번째 요소는 항상 가장입니다.

• 요소 추가 또는 로그 시간에 제거할 수 있습니다.

응용 프로그램의 범위,이 알고리즘을 적용 한 경우 더 이상 힙 후.

반드시 해당 요소의 상대적 순서 유지 되지 않습니다 때문에이 안정 된 정렬을 아닙니다.

힙 우선 순위 큐를 구현 하는 이상적인 방법 이며 표준 템플릿 라이브러리 컨테이너 어댑터 구현에 사용 되는 priority_queue 클래스.

참조 범위 유효 해야 합니다. 모든 포인터는 dereferenceable 이어야 하며 마지막 위치에서 첫 번째 접근할 시퀀스 내에서 증분 합니다.

복잡 한 개는 N 로그 N여기서 N = (_Last – _First).

예제

// alg_sort_heap.cpp
// compile with: /EHsc
#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
using namespace std;

void print(const string& s, const vector<int>& v) {
    cout << s << ": ( ";

    for (auto i = v.begin(); i != v.end(); ++i) {
        cout << *i << " ";
    }

    cout << ")" << endl;
}

int main() {
    vector<int> v;
    for (int i = 1; i <= 9; ++i) {
        v.push_back(i);
    }
    print("Initially", v);

    random_shuffle(v.begin(), v.end());
    print("After random_shuffle", v);

    make_heap(v.begin(), v.end());
    print("     After make_heap", v);

    sort_heap(v.begin(), v.end());
    print("     After sort_heap", v);

    random_shuffle(v.begin(), v.end());
    print("             After random_shuffle", v);

    make_heap(v.begin(), v.end(), greater<int>());
    print("After make_heap with greater<int>", v);

    sort_heap(v.begin(), v.end(), greater<int>());
    print("After sort_heap with greater<int>", v);
}

샘플 출력

Initially: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 9 2 7 3 1 6 8 4 5 )
     After make_heap: ( 9 5 8 4 1 6 7 2 3 )
     After sort_heap: ( 1 2 3 4 5 6 7 8 9 )
             After random_shuffle: ( 5 8 3 1 2 9 7 6 4 )
After make_heap with greater<int>: ( 1 2 3 4 5 9 7 6 8 )
After sort_heap with greater<int>: ( 9 8 7 6 5 4 3 2 1 )

요구 사항

헤더: <algorithm>

네임 스페이스: std

참고 항목

참조

heap

표준 템플릿 라이브러리