[자료구조] 우선순위 큐의 구현(3) - Delete, Insert

[자료구조] 우선순위 큐의 구현(3) - Delete , Insert

오늘은 우선순위 큐의 삽입, 삭제 과정에 대해 알아보도록 하겠다.

저번 시간에 두 자식 노드 중 우선순위가 높은 놈을 찾고, 자식이 없다면 0을 리턴하는 함수를 정의했다.

그 함수를 적극 활용하여 Delete 과정을 이해해 보도록 하자.

Delete 과정을 잘 이해한다면 Insert 과정 또한 쉽게 이해할 수 있을 것이다.

1. 우선순위 큐의 Delete 구현

2. 우선순위 큐 삭제의 과정

1. 가장 마지막 노드를 추출한다.

2. 인덱스 1번에 위치한 노드가 삭제되기 때문에 그 밑의 자식노드들과 마지막 노드의 우선순위를 비교한다.

3. 자식노드의 우선순위를 비교할 때, 저번 포스팅에서 정의한 GetHiPriChildIDX() 함수를 사용한다.

4. 현재의 노드가 마지막 노드보다 우선순위가 높다면 한칸 위로 이동한다. (1번이 빠졌기 때문에 공간을 메운다.)

5. 마지막 노드보다 우선순위가 낮거나, 자식노드가 더이상 없을 때, 마지막 노드의 자리가 결정된다.

3. 그림으로 이해(..?)

우선순위 큐의 Delete 구현 소스 우측에 적혀있는 번호와 위 그림의 번호의 동작과 일치한다. (그림이 쪼금 애매하다.)

쉽게 말해서, 힙의 마지막 데이터를 빼서, 가장 위쪽에서부터 차례로 비교를 해오면서 내려온다.

그리고 마지막 노드보다 우선순위가 높다면 한칸씩 위로 이동하게 해주는 것이다.

4. 우선순위 큐의 Insert 구현

5. 우선순위 큐의 삽입 과정

1. 힙의 마지막 자리에 새로운 노드를 배정 (실제로 넣지는 않고 가정만 한다.)

2. 그의 부모노드와 우선순위를 비교하여 위치 변경

3. 삭제의 과정이 위에서 밑으로 였다면, 삽입의 과정은 밑에서 위로

오늘은 우선순위 큐의 Delete와 Insert 과정에 대해 알아보았다.

다음 포스팅에서는 좀 더 유연성있게 우선순위를 정하는 힙에 대해 알아보도록 하겠다.