[C++] Heap Tree

Heap Tree, Priority Queue

 

when ?

데이터들 중 가장 큰 값 또는 가장 작은 값을 계속해서 추출해야 하는 필요성이 있을 때 사용

 

[ 구조 ]

우선은 이진 트리의 형태를 갖는다. (각 노드가 최대 2개의 자식 노드를 갖는 트리)

힙 트리의 구조를 유지하기 위해서 2가지 규칙이 존재한다. (공식용어는 아님)

 

( 규칙 1 )

[부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 커야함. (Predicate에 따라 다름)

: 위 조건만 만족한다면 어떻게든 괜찮다 (이진 탐색 트리보다 조건이 느슨함)

( 규칙 2 )

마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 함. (완전 이진 트리)

마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야 함.

위 2가지 구조를 통해 알 수 있는 규칙 2번

: 노드 개수를 알면, 트리 구조는 확정할 수 있다.

 

[ 규칙 2로 부터 각 노드의 위치 추론 ]

힙 트리는 이름이 트리인 것과 달리 vector를 통해 관리할 수 있는데,

1) i 번 노드의 왼쪽 자식은 [(2 * i) + 1] 번

2) i 번 노드의 오른쪽 자식은 [(2 * i) + 2] 번

3) i 번 노드의 부모는 [(i - 1) / 2] 번
으로 index가 정해진다.

=> C++ 기준이며, 언어 특성상 정수 나눗셈의 나머지는 버림되는 것을 이용한 것임.

 

 

[ 새로운 값 추가, push() ]

2번 규칙 : 우선 트리 구조부터 맞춰준다

=> 마지막 레벨 왼쪽부터 채워준다

그 다음, 1번 규칙을 통해 추가된 값이 현재 부모 노드 값보다 큰지? 확인하며 큰 값일 경우, 계속 부모 노드와 swap하며 위로 올라간다.

 

[ 최대값 꺼내기, pop() ]

최대값을 pop()으로 꺼낸 뒤, 제일 상단의 루트 노드가 없어진 상태일 것이다. 여기서

2번 규칙 : 제일 마지막에 위치한 데이터(마지막 레벨 가장 오른쪽)를 루트 노드로 옮긴다.

그 다음 아래 2개의 자식 노드 중, 더 큰 값과 비교해서 더 작다면 자식 노드와 swap하며 역으로 내려간다.

 

[ 시간복잡도 ]

힙 트리를 이용한다면 왼쪽 혹은 오른쪽으로 내려갈 때 마다, 데이터의 절반을 제외할 수 있어

push와 pop 둘 다 O(logN)의 시간복잡도를 가지게 된다.

 

[ 정리 ]

2번 규칙을 통해 노드 개수로 트리의 구조를 알 수 있으며, push와 pop 내부 에서 1번 규칙을 통해 노드들을 서로 swap 해가며 트리 구조를 유지할 수 있다.

 

 

[ 구현 연습 ]

(가독성을 위해 size()의 int casting은 제거했음)

// 규칙 1) : 부모노드의 값은 자식노드의 값 보다 항상 커야함
// 규칙 2) : 노드 개수를 알면, 구조를 확정할 수 있다 (마지막 레벨을 제외한 모든 노드 꽉 차있어야 함, 마지막 레벨의 노드는 왼쪽부터 채워져야 함)
// 규칙 2로 부터 각 노드의 위치 추론) : i의 [left : 2*i + 1], [right : 2*i + 2], [parent : (i-1) / 2]
template<typename T, typename Container = vector<T>, typename Predicate = less<T>>
class PriorityQueue
{
public:
    void push(const T& value)
    { // : 마지막 레벨의 좌측으로 부터 마지막 노드에 추가, 그리고 부모(next)와 계속 비교하며 부모보다 크다면 swap
        _heap.push_back(value);
 
        int now = _heap.size() - 1;
 
        while (now > 0)
        {
            int next = (now - 1) / 2;
            if (_predicate(_heap[now], _heap[next]))
                break;
 
            // 부모 - 자식 교체
            ::swap(_heap[now], _heap[next]);
            now = next;
        }
    }
 
    void pop()
    { // 가장 마지막 노드를 비어있는 루트 노드로 옮긴 뒤, 2개의 자식 노드와 비교하며 자식 노드가 더 클 경우 계속해서 swap, 이 때, 각 자식노드는 _heap의 경계를 벗어나는지 확인해야 함
        _heap[0] = _heap.back();
        _heap.pop_back();
 
        int now = 0;
        while (true)
        {
            int left = 2 * now + 1;
            int right = 2 * now + 2;
 
            if (left >= _heap.size())
                break;
 
            int next = now;
 
            if (_predicate(_heap[next], _heap[left]))
                next = left;
 
            if (right < _heap.size() && _predicate(_heap[next], _heap[right]))
                next = right;
 
            if (now == next)
                break;
            
            ::swap(_heap[now], _heap[next]);
            now = next;
        }
    }
 
    T& top() { return _heap[0]; }
 
    bool empty() const { return _heap.empty(); }
    int size() const { return _heap.size(); }
 
private:
    Container _heap = {};
    Predicate _predicate = {};
};
 
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    PriorityQueue<int, vector<int>, less<int>> pq;
 
    pq.push(100);
    pq.push(200);
    pq.push(300);
    pq.push(400);
    pq.push(500);
    pq.push(200);
    pq.push(300);
    pq.push(400);
    pq.push(500);
 
    while (!pq.empty())
    {
        const int value = pq.top();
        pq.pop();
 
        cout << value << "\n";
    }
 
    return 0;
}

 

std::priority_queue와 동일한 결과

 

 

 

 

 

[ Reference : Rookiss의 C++ Part3 : 자료구조 ]