Deap(더블 엔디드 힙) 자료구조에 요소 삽입하는 방법

Deap에 요소 삽입하기

Deap(Double-Ended Heap, 더블 엔디드 힙)은 최솟값과 최댓값을 모두 효율적으로 관리할 수 있는 힙 기반 자료구조입니다. Deap에 새로운 요소를 삽입하려면 먼저 최솟값과 최댓값의 위치를 계산하는 절차가 필요합니다.

최솟값 및 최댓값 계산 절차

Deap에서 특정 위치 m을 기준으로 대응되는 최솟값과 최댓값의 위치를 구하는 절차는 다음과 같습니다.

min_value(m): Deap에서 최솟값의 위치를 계산합니다.
return m − 2^{log₂(m−1)}

max_value(m): Deap에서 최댓값의 위치를 계산합니다.
return m + 2^{log₂(m−1)}

삽입 연산의 단계

Deap 자료구조에서의 삽입 연산은 다음 순서로 진행됩니다.

• 힙 배열 b[]에 대해, 위치 m이 Deap의 최대 힙(maximum-heap) 영역 내에 있는지 확인합니다.
• 위에서 정의한 절차를 이용해 Deap 내의 최솟값과 최댓값의 위치를 계산합니다.
• 왼쪽 서브트리(최소 힙)와 오른쪽 서브트리(최대 힙)의 키 값을 서로 비교합니다.
• 마지막으로, 아래 알고리즘에 따라 실제 삽입 연산을 수행합니다.

Deap 삽입 알고리즘

Procedure deap_insertion(b[], y, m):
if (m == 1)
    b[2] = y;
else {
    if (m is in maximum subtree) {
        index = min_value(m);
        if (y < b[index]) {
            b[m] = b[index];
            insert y in minimum subtree;
        }
        else
            insert y in maximum subtree;
    } else {
        index = max_value(m);
        if (y > b[index]) {
            b[m] = b[index];
            insert y into maximum subtree;
        }
        else
            insert y into minimum subtree;
    }
}

이 알고리즘의 핵심 아이디어는 다음과 같습니다. 삽입하려는 값 y가 최대 힙 영역에 속한다면, 그 위치에 대응하는 최소 힙의 값과 비교하여 y가 더 작으면 두 값을 교환한 뒤 최소 힙 쪽에 삽입하고, 그렇지 않으면 최대 힙 쪽에 그대로 삽입합니다. 반대로 y가 최소 힙 영역에 속한다면 대응하는 최대 힙의 값과 비교하여 y가 더 크면 교환 후 최대 힙에 삽입하고, 아니면 최소 힙에 삽입합니다. 이러한 과정을 통해 Deap은 항상 최소 힙과 최대 힙 간의 대칭성 조건을 유지하며, O(log n) 시간 복잡도로 삽입 연산을 수행할 수 있습니다.