C++ - 힙 관련 STL(make_heap, push_heap, pop_heap)

<algorithm>헤더를 추가할 것!

 

이 포스트에서 다루는 함수들은 정확히는 vector의 원소들을 힙의 형태를 띄도록 재배치한다. 따라서 vector 관련 함수가 함께 쓰여야 한다.

 

make_heap()

시간복잡도: O(n)으로 구현되어 있다.

 

사용법:

1) make_heap(v.begin(), v.end());

v라는 vector의 원소들끼리 서로 순서를 바꾸어 max heap이 되도록 한다. 

 

2) make_heap(v.being(), v.end(), cmp);

그런데 max heap이 아니라 min heap을 만들고 싶다면? sort함수처럼 위와 같이 비교함수(cmp)를 작성해서 인자로 넣으면 된다.

 

 

코드 예시:

bool cmp(int a, int b) {
    if (a > b) return true;
    else return false;
}

 

int main() {
    vector<int> v = { 1, 2, 3, 4, 8, 7, 6, 5 };
    for (auto i : v) cout << i << ' ';
    cout << '\n';

    make_heap(v.begin(), v.end());
    for (auto i : v) cout << i << ' ';
    cout << '\n';

    make_heap(v.begin(), v.end(), cmp);
    for (auto i : v) cout << i << ' ';
    cout << '\n';

    return 0;
}

 

출력:

1 2 3 4 8 7 6 5

8 5 7 4 2 3 6 1

1 2 3 4 8 7 6 5

 

push_heap()

시간복잡도: O(logn)으로 구현되어 있다.

 

사용법:

make_heap(v.begin(), v.end());

v.push_back(9);

push_heap(v.begin(), v.end());

 

우선 vector를 힙 구조로 바꿔준 다음, v.push_back(원소) -> push_heap(시작, 끝)순으로 함수를 부르며 힙에 원소를 삽입한다. 마찬가지로!!! 만일 min heap이라면 비교함수 cmp를 push_heap(v.begin(), v.end(), cmp)와 같은 형태로 넣어줘야 한다.

 

 

코드 예시:

int main() {
    vector<int> v = { 1, 2, 3, 4, 8, 7, 6, 5 };
    make_heap(v.begin(), v.end());
    for (auto i : v) cout << i << ' ';
    cout << '\n';

    v.push_back(9);
    push_heap(v.begin(), v.end());
    for (auto i : v) cout << i << ' ';
    cout << '\n';
    
    return 0;
}

 

출력:

8 5 7 4 2 3 6 1

9 8 7 5 2 3 6 1 4

 

pop_heap()

시간복잡도: O(logn)으로 구현되어 있다.

 

사용법:

make_heap(v.begin(), v.end());

pop_heap(v.begin(), v.end());

v.pop_back();

 

우선 vector를 힙 구조로 바꿔준 다음, pop_heap(시작, 끝) -> v.pop_back()순으로 함수를 부르며 힙에서 원소를 삭제한다. 마찬가지로!!! 만일 min heap이라면 비교함수 cmp를 pop_heap(v.begin(), v.end(), cmp)와 같은 형태로 넣어줘야 한다.

 

 

코드 예시:    

int main() {
    vector<int> v = { 1, 2, 3, 4, 8, 7, 6, 5 };
    make_heap(v.begin(), v.end());
    for (auto i : v) cout << i << ' ';
    cout << '\n';

    pop_heap(v.begin(), v.end());
    v.pop_back();
    for (auto i : v) cout << i << ' ';
    cout << '\n';

    return 0;
}

 

출력:

8 5 7 4 2 3 6 1

7 5 6 4 2 3 1