오늘은 자료구조중에 이진트리에서의 힙의 삭제에 대한 내용을 작성해보려 합니다.

힙에서의 삭제 연산은 언제나 최상위 노드에 있는 원소를 삭제하여 반환합니다.

그래서 최대 힙에서의 삭제 연산은 키값이 가장 큰 원소를 삭제하여 반환하고 최소 힙에서의 삭제 연산은 키갓이 가장 작은 원소를 삭제하여 반환됩니다.

힙의 삭제 연산에서 중요한 것은 최상위 노드의 원소를 삭제한 뒤에도 완전 이진 트리의 형태와 노드의 키 값에 대한 힙의 조건이 유지 되어야 합니다.

방식

1. 루트 노드의 heap[1]을 item 변수에 저장합니다.

2. 마지막 노드의 heap[n]을 tmp 변수에 일단 저장합니다.

3. 마지막 노드를 삭제합니다.

4. 마지막 노드의 원소인 tmp의 임시 저장위치 i는 루트 노드인 1번 자리로 됩니다.

5. 현재 저장 위치에서 왼쪽 서브 노드와 오른쪽 서브 노드가 있을 때에는 둘 중 큰 노드를 왼쪽 노드로 만들고, 그 값이랑 삭제된 노드를 비교하여 삭제된 노드가 크다면, 현재의 임시 위치를 tmp 자리로 만듭니다.

6. 만약 tmp가 하위 노드보다 작으면 하위 노드와 자리를 바꾸면서 다시 전의 단계로 돌아가서 반복합니다.

7. 위 두 단계를 반복하면서 위치를 찾습니다.

8. 찾은 위치애서 tmp를 저장하며 최대힙을 재구성합니다.

9. 루트 노드를 저장한 item을 반환하면서 연산을 마칩니다.

알고리즘

func()
    if(n=0) then 
        return false;
    item <- heap[1];
    tmp <- heap[n];
    n <- n-1;
    i <- 1;
    j <- 2;
    while(j<=n) do{
        if(j<n) then
            if(heap[j]<heap[i+j]) then 
            j <- j+1;
        if(tmp >= heap[j]) then 
            exit;
        heap[i] <- heap[j];
        i <- j;
        j <- j*2;
    }
    heap[i] <- tmp;
    return item;
end()