Queue 와 Priority Queue

 

 

/* Queue , Priority Queue */

Queue 는 FIFO 형식으로 먼저 넣은 데이터가 먼저 나오는 구조입니다.

Priority Queue 는 넣은 데이터의 순서와 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

/* Priority Queue의 구조 */

Heap 구조와 동일하다. 완전 이진트리 구조이다. 편의성을 위해 Array로 구현. (0번 인덱스는 사용 X)

 

MaxHeap 과 MinHeap 이 있다. (root node의 값이 max, min 인지에 갈린다)

 

/* Priority Queue - PUSH */

190을 PUSH 하면

 

 

마지막 인덱스에 저장한다.

 

부모노드의 크기와 비교하여 노드 구조를 바꾼다.

/* Priority Queue - POP */

 

root 노드의 값을 pop하고 마지막 인덱스인 100 노드를 root에 위치시킨다.

 

100이 자식의 노드보다 작으므로 자식 노드들 중에서 큰 값과 swap 한다.

 

해당 작업을 반복한다

/* 시간복잡도 */

push, pop 모두 O(log n)의 시간복잡도를 가진다.