Move Fast

힙 알고리즘 (Heap Algorithm)

• Heap (위키백과)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다. 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

• make_heap 범위 내 원소들을 힙 속성을 만족하도록 만듬.

  • push_heap 힙에 원소를 삽입. (컨테이너가 힙 속성을 만족한다고 가정함.)

  • pop_heap 힙에 원소를 제거. (컨테이너가 힙 속성을 만족한다고 가정함.)

// until C++20
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );

// since C++20
template< class RandomIt >
constexpr void make_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void make_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
constexpr void push_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void push_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
constexpr void pop_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void pop_heap( RandomIt first, RandomIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

void print(string msg, vector<int> &v) {
    cout << msg;
    for (auto i : v) cout << i << ' ';
    cout << endl;
}

int main() {
    cout << "Max heap:" << endl;
    vector<int> v { 3, 2, 4, 1, 5, 9 };
    print("initially, v: ", v);

    make_heap(v.begin(), v.end());
    print("after make_heap, v: ", v);

    v.push_back(6);
    print("before push_heap, v: ", v);

    push_heap(v.begin(), v.end());
    print("after push_heap, v: ", v);

    pop_heap(v.begin(), v.end());
    print("after pop_heap, v: ", v);

    auto top = v.back();
    v.pop_back();
    cout << "former top element: " << top << endl;
    print("after removing the former top element, v: ", v);

    cout << endl << "Min heap:" << endl;
    vector<int> v1 { 3, 2, 4, 1, 5, 9 };
    print("initially, v1: ", v1);

    make_heap(v1.begin(), v1.end(), greater<>{});
    print("after make_heap, v1: ", v1);

    v.push_back(6);
    print("before push_heap, v: ", v);

    push_heap(v.begin(), v.end());
    print("after push_heap, v: ", v);

    pop_heap(v1.begin(), v1.end(), greater<>{});
    print("after pop_heap, v1: ", v1);

    auto top1 = v1.back();
    v1.pop_back();
    cout << "former top element: " << top1 << endl;
    print("after removing the former top element, v1: ", v1);

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
before push_heap, v: 9 5 4 1 2 3 6
after push_heap, v: 9 5 6 1 2 3 4
after pop_heap, v: 6 5 4 1 2 3 9
former top element: 9
after removing the former top element, v: 6 5 4 1 2 3

Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
before push_heap, v: 6 5 4 1 2 3 6
after push_heap, v: 6 5 6 1 2 3 4
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5
 */

• sort_heap 힙의 원소들을 정렬.

  • 시간 복잡도: O( 2 * N * log(N) ), 범위의 크기 = N

// until C++20
template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp );

// since C++20
template< class RandomIt >
constexpr void sort_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void sort_heap( RandomIt first, RandomIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v{3, 1, 4, 1, 5, 9};

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

    cout << "heap:\t";
    for (const auto &i : v) cout << i << ' ';
    cout << endl;

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

    cout << "sorted:\t";
    for (const auto &i : v) cout << i << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
heap:	9 5 4 1 1 3
sorted:	1 1 3 4 5 9
 */

• is_heap 힙 속성을 만족하면 true, 그렇지 않으면 false를 반환.

  • is_heap_until 힙 속성을 만족하지 않는 첫번째 원소를 반환.

// since C++11 until C++20
template< class RandomIt >
bool is_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
bool is_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
RandomIt is_heap_until( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );

// since C++20
template< class RandomIt >
constexpr bool is_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr bool is_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
constexpr RandomIt is_heap_until( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class RandomIt >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt, class Compare >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );

template< class ExecutionPolicy, class RandomIt >
RandomIt is_heap_until( ExecutionPolicy&& policy, RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt, class Compare >
RandomIt is_heap_until( ExecutionPolicy&& policy,
                        RandomIt first, RandomIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

void print(string msg, vector<int> &v) {
    cout << msg;
    for (auto i : v) cout << i << ' ';
    cout << endl;
}

int main() {
    vector<int> v { 3, 1, 4, 1, 5, 9 };
    print("initially, v: ", v);

    if (!is_heap(v.begin(), v.end())) {
        cout << "making heap..." << endl;
        make_heap(v.begin(), v.end());
    }

    print("after make_heap, v: ", v);

    cout << "probably mess up the heap" << endl;
    v.push_back(2);
    v.push_back(6);

    auto heap_end = is_heap_until(v.begin(), v.end());
    print("all of v: ", v);

    cout << "only heap: ";
    for (auto i = v.begin(); i != heap_end; ++i) cout << *i << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
initially, v: 3 1 4 1 5 9
making heap...
after make_heap, v: 9 5 4 1 1 3
probably mess up the heap
all of v: 9 5 4 1 1 3 2 6
only heap: 9 5 4 1 1 3 2
 */