[자료구조] 우선순위 큐의 이해(2)

[자료구조] 우선순위 큐의 이해(2)

1. 우선순위 큐를 구현하기 위해 힙(heap)을 사용한다.

2. 우선순위 큐는 꼭 만족해야 하는 조건이 있다.

(1) 완전 이진 트리

(2) 자식노드의 우선순위 <= 부모노드의 우선순위

3. 힙(heap)의 삽입 과정 (출처 : 윤성우의 열혈 자료구조)

4. 힙(heap)의 삭제 과정 (출처 : 윤성우의 열혈 자료구조)

--> 루트의 우선순위가 가장 높기 때문에 (만족 조건2) 루트를 빼준다.

--> 마지막 노드가 루트 노드로 위치한 뒤, 자기자리를 찾아가는 과정에서 두 서브트리 중 우선순위가 높은 쪽과 교환하게 된다.

5. 삽입과 삭제 과정에서 보이는 성능 평가

(1) 배열 기반 우선순위 큐                                 삽입 : O(n)            --> 저장된 데이터 수 만큼 비교가 일어난 뒤에 자리를 찾게 된다.

  삭제 : O(1)

(2) 연결 리스트 기반 우선순위 큐                     삽입 : O(n)             -- 저장된 데이터 수 만큼 비교가 일어난 뒤에 자리를 찾게 된다.

  삭제 : O(n)

(3) 힙(heap) 기반 우선순위 큐                         삽입 : O(log2n)

  삭제 : O(log2n)

       

--> 4층 높이의 힙이 있다고 치면, 이는 각각의 우선순위에 따라 위치가 정해져 있을 것이다.

--> 삽입을 하기 위해서 루트 노드부터 우선순위를 비교를 해나간다.

--> 한 층에 한번씩만 비교연산을 하게 되면 자리를 찾게된다. (트리는 내려가면서 자리가 결정되는 구조이다.)