[자료구조] 우선순위 큐 (수정) :: 늦깎이 IT

---

이 포스팅은 이전에 정리했던 "우선순위 큐"에 대해서 핵심적인 부분만을 다시 작성한 포스팅입니다. 

[이전 포스팅]

2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙

2019/02/16 - [알고리즘 이론] - [정렬] 힙 정렬 :: 늦깎이 IT

---

[우선순위 큐]

먼저 입력된 데이터가 먼저 처리되는 일반적인 FIFO큐와는 달리 우선순위 큐는 입력의 순서에 상관없이 우선순위가 높은 데이터를 먼저 처리하는 자료구조이다.

우선순위 큐는 힙과 밀접한 관계가 있으므로, 힙에 대한 내용은 이전 포스팅을 참고하기 바란다.

2019/04/16 - [알고리즘 이론] - [정렬] 힙 정렬 (수정) :: 늦깎이 IT

[데이터 삽입 하기]

데이터가 힙에 추가될 때에는 힙이 "완전 이진트리"라는 점을 명심해야 한다. "완전 이진트리"는 마지막 레벨을 제외한 모든 레벨은 노드들로 꽉차있고, 마지막 레벨은 왼쪽부터 순서대로 채워지기 때문이다. 그러므로 아래의 그림처럼, 새로 추가되는 데이터는 힙의 마지막 레벨, 맨 오른쪽에 추가되어야 한다.

아래와 같은 힙에 18이라는 데이터를 추가한다고 가정해보자. 그러면 마지막 레벨의 맨 오른쪽의 위치에 데이터가 삽입된다.

18이라는 값이 힙에 저장된 직후 힙의 구조를 살펴보면 최대힙의 전제조건이 깨진 것을 확인할 수 있다.

18과 5의 관계를 보면, 부모 노드는 자식 노드들보다 값이 크다는 최대힙의 전제조건에 맞지 않는다.

그렇기 때문에 자식노드에서 루트노드까지 올라가며 부모와 비교를 진행해야 한다.

18의 부모노드인 5의 위치에서 Heapify를 진행하여 5와 18의 위치를 바꾼다. 그 이후 18의 부모노드인 16에서 Heapify를 진행함으로써 16과 18의 위치를 바꾼다.

[의사 코드]

MAX-HEAP-INSERT(A, key)
    length ← 1 + length of A[]
    A[length] = key
    i = length
 
    while(i > 1 and A[Parent[i]] < A[i])
        swap A[i] and A[Parent[i]]
        i = Parent[i]

[시간 복잡도]

데이터를 삽입하는 데 걸리는 시간은 O(1)이고, 마지막 단말 노드부터 루트노드까지 부모 노드와 비교 연산을 진행하는 시간복잡도는 O(logN)이다.

[데이터 삭제하기]

힙에서 데이터를 삭제할 때 유의할 것은, 우선순위 큐는 우선순위가 높은 순서대로 삭제(확인)할 수 있다는 것이다.

아래와 같은 그림에서 우선순위가 가장 높은 데이터는 힙의 루트노드에 저장되어 있으므로, 루트노드를 반환해야 한다. 

18이라는 데이터를 반환하고 나면, 루트노드가 비어있는 상태로 변하는데, 힙이 "완전 이진트리"라는 점을 감안하면 맨 마지막에 있던 단말노드가 루트 노드의 자리를 채워야 하는 것을 알 수 있다.

정확히 말하자면 맨 마지막 노드가 아닌 힙의 전제조건을 만족시키면서 노드들을 앞으로 루트노드쪽으로 전진시키는 것이 직관적일 수 있다.

그러나, 위 그림의 두 번째처럼 맨 마지막 단말 노드를 루트 노드의 위치에 갖다 놓게되면 왼쪽 서브트리와 오른쪽 서브트리는 여전히 힙의 전제조건을 만족함을 알 수 있다.

즉, 루트노드에 대해서 Heapify 연산을 한 번 진행하면 트리 전체가 힙의 전제조건을 만족시킬 수 있다.

[의사 코드]

MAX-HEAP-DELETE(A)
    if length of A < 1
        then error "Heap underflow"
    
    max ← A[1]
    A[1] ← A[length of A]
    length ← length - 1
    Heapify(A, 1)
    return max

[시간 복잡도]

데이터를 삭제하는 데 걸리는 시간은 O(1)이고, 루트노드부터 Heapify를 진행하는 O(logN)이다.

[참고]

[이미지 출처]

[ratsgo's blog]