대칭 최소-최대 힙(SMMH)

대칭 최대-최소 힙(SMMH, symmetric min-max heap) 은 양쪽 끝 우선순위 큐를 표현할 수 있는 자료구조이다. 양쪽 끝 우선순위 큐(double-ended priority queue)는 일반적인 우선순위 큐와 달리 최소 우선순위 원소의 반환과 삭제, 최대 우선순위 원소의 반환과 삭제를 동시에 지원하는 자료구조이다.

SMMH는 루트를 제외한 노드들이 하나의 원소를 갖는 완전 이진 트리이다. 루트는 공백이고, 각 노드는 아래 조건을 만족한다.

1. 임의의 노드 N의 왼쪽 자식은 N의 서브트리의 원소 중 최소 원소를 갖는다. (존재한다면)
2. 노드 N의 오른쪽 자식은 N의 서브트리의 원소 중 최대 원소를 갖는다. (존재한다면)

SMMH 예시

위 그림은 SMMH의 예를 보여준다. 노드 N을 10을 가진 노드라 할 때 왼쪽 자식으로 서브트리 중 최소 원소인 19를 갖고, 오른쪽 자식으로 최대 원소인 68을 갖는다. 다른 노드에 대해서도 위 조건을 만족함을 확인할 수 있다.

SMMH 성질

아래 조건이 참이면서 루트가 공백인 완전 이진 트리는 SMMH이다.

• P1. 각 노드의 원소는 오른쪽 형제 원소보다 작거나 같다.
• P2. 조부모를 가진 모든 노드에 대해, 조부모의 왼쪽 자식에 있는 원소는 작거나 같다.
• P3. 조부모를 가진 모든 노드에 대해, 조부모의 오른쪽 자식에 있는 원소는 크거나 같다.

위 성질을 이용해 원소를 삽입하고, 삭제하는 알고리즘을 도출할 수 있다. 아래에 위 성질들을 각각 P1, P2, P3로 표현한다.

SMMH 표현

SMMH는 완전 이진 트리이므로, 배열을 사용하여 효율적으로 표현할 수 있다. 배열의 인덱스 0은 사용하지 않고, 인덱스 1은 루트 노드로 공백으로 비워둔다. 그리고 각 노드의 (인덱스 * 2)에는 왼쪽 자식 노드, (인덱스 * 2 + 1)에는 오른쪽 자식 노드를 저장한다.

SMMH 예시의 배열 표현 예시

위 그림에서의 SMMH 예시를 배열로 표현하면 위와 같다.

SMMH 삽입 과정

• 단계 1 : 트리의 크기를 1 확장하고, 삽입될 원소 x를 위한 새로운 노드 E를 생성한다. 이 노드는 새로운 원소 x를 삽입할 후보 노드가 된다.
• 단계 2 : E로 x를 삽입한 결과가 P1에 위배되는지 검증한다. E가 오른쪽 자식이고, x가 왼쪽 자식보다 작을 때 위배된다. P1에 위배되는 경우, E의 형제 원소는 E로 이동되고, E는 형제 노드로 이동한다.
• 단계 3 : E로부터 트리 위쪽으로 P2와 P3을 검증하면서 bubble-up 패스를 수행한다. bubble-up 패스를 할 때마다 E는 한 레벨씩 트리 위로 이동한다. P2와 P3에 위배되지 않는 곳에 E가 위치했을 때, x를 E에 삽입한다.

SMMH 원소 삽입 1

위의 SMMH에 새로운 원소 4를 삽입하는 과정을 살펴보자. 트리의 크기를 확장하여 삽입할 노드 후보 E를 생성한다. E는 왼쪽 자식이므로 P1에 위배되지 않는다. 조부모의 왼쪽 자식의 원소 25가 4보다 크므로, P2에 위배된다. 따라서 E는 원소 25의 노드로 이동하고, 현재 E의 원소는 25로 교환된다.

SMMH 원소 삽입 2

P2 또는 P3에 위배되어 bubble-up하게 되면 새로운 부모의 서브트리의 원소 중 최소 또는 최대임이 확실하므로 P1은 확인할 필요 없다. 새로운 조부모 루트의 왼쪽 자식의 원소 10이 4보다 크므로, P2에 위배된다. 따라서 E는 원소 10의 노드로 이동하고, 현재 E의 원소는 10으로 교환된다.

SMMH 원소 삽입 3

새로운 후보 노드 E는 조부모가 존재하지 않으므로, P2와 P3 모두 위배되지 않는다. 따라서 현재 E의 위치에 원소 4가 삽입된다. 새로운 노드와 위치가 변경된 노드들이 모두 SMMH의 성질을 만족하는 걸 확인할 수 있다.

최대 bubble-up 횟수가 트리의 높이와 같고, 각 노드에서 상수 시간이 걸리므로 SMMH의 삽입 시간복잡도는 O(logn)이다. 위 단계를 코드로 아래와 같이 구현할 수 있다.

class SMMH {
    int* heap; /* heap은 크기가 SIZE인 1차원 배열 */
    int last; /* last는 마지막 노드의 인덱스를 가리키는 멤버 변수 */
    (중략)
    void push(int node) {
        if (last >= SIZE - 1) {
            cerr << "Heap full." << '\n';
            return;
        }

        int candidate = ++last;

        // P1 검증
        if (candidate % 2 == 1 && node < heap[candidate - 1]) {
            /* P1에 위배되면 왼쪽 형제 노드와 후보 노드 교환 */
            heap[candidate] = heap[candidate - 1];
            candidate = candidate - 1;
        }

        bool done = false;
        while (!done && 4 <= candidate) {
            /* P2와 P3 만족하지 않고, 조부모 노드가 존재하는 동안 반복 */
            int grandparent = candidate / 4;
            int leftOfGrandparent = 2 * grandparent;
            int rightOfGrandparent = leftOfGrandparent + 1;

            // P2 검증
            if (node < heap[leftOfGrandparent]) {
                /* P2에 위배되면 조부모의 왼쪽 자식과 교환 */
                heap[candidate] = heap[leftOfGrandparent];
                candidate = leftOfGrandparent;
            }
            // P3 검증
            else if (heap[rightOfGrandparent] < node) {
                /* P3에 위배되면 조부모의 오른쪽 자식과 교환 */
                heap[candidate] = heap[rightOfGrandparent];
                candidate = rightOfGrandparent;
            }
            else
                done = true;
        }
        heap[candidate] = node;
    }
    (후략)
}

SMMH 삭제 과정 (최소 원소)

SMMH의 최소 원소는 루트의 왼쪽 자식, 최대 원소는 루트의 오른쪽 자식이다. 그러면 SMMH에서 최소 원소를 삭제하는 과정은 다음과 같다.

• 단계 1 : 트리의 마지막 노드를 x에 저장하고, 트리의 크기를 1 줄인다. 그리고 루트의 왼쪽 자식이 x를 재삽입할 후보 노드 E가 된다.
• 단계 2 : E에 x를 삽입하면 P2에 위배되는지 검증한다. E의 왼쪽 자식과 오른쪽 형제 노드의 왼쪽 자식(존재하면) 중 최소 노드가 x보다 작으면, 해당 원소는 E로 이동되고, E는 해당 노드로 이동한다.
• 단계 3 : 새로운 E가 P1을 만족하는지 검증한다. E의 오른쪽 형제 노드가 x보다 작으면 오른쪽 형제 노드의 원소와 x를 교환한다.
• 단계 4 : 단계 2와 단계 3을 반복하면서 E가 P1과 P2를 만족할 때까지 trickle-down 패스를 진행한다. P1과 P2를 만족할 때 E에 원소 x를 삽입한다.

* 최소 원소를 삭제하는 과정에서는 P3 만족이 보장되므로 P3에 위배되는지 확인할 필요 없다.

SMMH 최소 원소 삭제 1

새로운 원소를 삽입한 SMMH에서 최소 원소를 삭제하는 과정을 살펴보자. 트리의 마지막 노드 원소인 25를 x에 저장하고, 트리의 크기를 1 줄인다. 최소 원소가 위치해 있던 루트의 왼쪽 자식 노드는 25를 재삽입할 후보 노드가 된다. E의 왼쪽 원소 19와 E의 형제 노드의 왼쪽 원소 10 중 10이 작고, x가 10보다 작으므로 P2에 위배된다. 따라서 원소 10은 E로 이동되고, E는 원소 10의 노드로 이동한다.

SMMH 최소 원소 삭제 2

새로운 E가 P1에 위배되는지 확인한다. P1에 위배되면 x의 값 25와 87을 교환해야 하지만, x가 87보다 작으므로, P1에 위배되지 않는다. 다시 P2에 위배되는지 확인하면, x가 E의 왼쪽 원소 34보다 크므로 P2를 만족한다. 따라서 현재 E에 25가 재삽입된다.

최대 trickle-down 횟수 또한 트리의 높이와 같으므로 SMMH의 삭제 시간복잡도는 O(logn)이다. 위 단계를 코드로 아래와 같이 구현할 수 있다.

class SMMH {
    int* heap; /* heap은 크기가 SIZE인 1차원 배열 */
    int last; /* last는 마지막 노드의 인덱스를 가리키는 멤버 변수 */
    (중략)
    void pop_min() {
        if (last == 1) {
            cerr << "Heap empty." << '\n';
            return;
        }
        else if (last == 2) {
            last--;
            return;
        }
        /* 마지막 노드가 node에 저장되고, 트리의 크기를 줄인다 */
        int node = heap[last--];
        int candidate = 2;

        bool done = false;
        while (!done && candidate * 2 <= last) {
            /* P1, P2 만족하지 않고, 후보 노드의 자식이 존재하는 동안 */
            int leftChild = candidate * 2;
            int siblingLeftChild = (candidate + 1) * 2;
            
            /* 후보 노드의 왼쪽 자식과 형제 노드의 왼쪽 자식 중 최소 노드를 찾는다 */
            int minChild = leftChild;
            if (siblingLeftChild <= last && heap[siblingLeftChild] < heap[minChild])
                minChild = siblingLeftChild;

            if (heap[minChild] < node) {
                /* P2 검증 : 찾은 최소 노드보다 node가 크면 교환한다 */
                heap[candidate] = heap[minChild];
                candidate = minChild;

                // P1 검증
                if (candidate + 1 <= last && heap[candidate + 1] < node) {
                    /* P1에 위배되면 node(x)의 값을 형제 노드와 교환한다. */
                    heap[candidate] = heap[candidate + 1];
                    heap[candidate + 1] = node;
                    node = heap[candidate];
                }
            }
            else
                done = true;
        }

        heap[candidate] = node;
    }
    (후략)
}

소스코드

대칭 최소-최대 힙을 완전한 클래스로 구현하여 삽입, 최소 삭제, 최대 삭제 등 멤버 함수가 포함된 C++ 소스코드는 아래 파일을 다운로드하여 확인할 수 있다.

SMMH.cpp

0.00MB