Deap(더블엔디드 힙)에서 최소 요소 삭제하기

Deap에서 최소 요소 삭제 개요

이번 장에서는 Deap(더블엔디드 힙) 자료구조에서 최솟값을 삭제하는 기법에 대해 알아보겠습니다. Deap의 삭제 연산은 트리의 루트에 위치한 최솟값을 제거하는 것을 목표로 합니다.

Deap은 완전 이진 트리 형태를 유지하므로 트리의 높이는 항상 log n입니다. 따라서 삭제 연산 역시 O(log n)의 시간 복잡도로 수행됩니다.

삭제 연산의 동작 원리

Deap에서 삭제가 일어나는 과정은 다음과 같습니다.

1단계: 먼저 배열에 저장된 요소의 개수(m)를 확인합니다. m이 2보다 작다면 삭제할 요소가 없으므로 그대로 종료합니다.

2단계: 최솟값 서브트리의 루트(b[2])에 있는 값을 임시로 저장합니다. 이 값이 곧 삭제될 최솟값입니다.

3단계: 마지막 위치의 요소(y)를 가져와 최솟값 서브트리의 빈자리를 채우며 아래로 내려갑니다. 이때 각 단계에서 두 자식 중 더 작은 값을 가진 노드와 비교하여, 해당 위치의 값이 y보다 크면 자식 값을 위로 올리고 y를 계속 아래로 이동시킵니다.

4단계: 내려가던 경로의 마지막 위치에서 대응되는 최댓값 서브트리의 형제 노드(k)를 찾습니다. 만약 k 위치의 값이 y보다 작다면, 두 값을 교환한 후 y를 최댓값 서브트리에 삽입하고 Deap의 성질을 복원합니다. 그렇지 않으면 y를 최솟값 서브트리에 삽입합니다.

Deap 삭제 의사 코드

Procedure deap_deletion(b[],m):
if(m<2)
   return; //There are no elements.
min=b[2]; //Minimum value is saved
for (i=2;2*i<=m;b[i]=b[k],i=k){
   k=i*2;
   If(k+1<=m && b[k]>b[k+1])
      k++;
   }
   k=max_value(i);
   if(x>b[k]){
      b[i]=b[k];
      insert y into maximum subtree;
   } else {
      insert y into minimum subtree;
}

정리

Deap의 최소 요소 삭제는 힙 정렬과 유사하게 루트의 값을 제거한 뒤, 마지막 요소를 재배치하면서 트리의 균형을 유지하는 방식으로 진행됩니다. 트리의 높이가 log n으로 제한되기 때문에 삽입 및 삭제 연산 모두 O(log n) 시간 안에 효율적으로 처리할 수 있다는 점이 Deap의 가장 큰 장점입니다.