우선순위 큐

강의 출처 : https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC

• Queue 큐

- 선입선출 (FIFO - IN - FIRST - OUT)

 

데이터를 큐에 enqueue 하게 되면 dequeue 하게되면 먼저 들어온 순서대로 출력

이때 먼저와 나중으로 시간 순서에 따라 데이터 추출이 이루어지기 때문에 Array List 혹은 Linked List로 구현했었다.

 

• Pirority Queue 우선순위 큐

- 우선순위가 가장 높은 값이 먼저 추출

 

시간 순서가 아닌 우선순위가 높은 것 부터 dequeue()

 

결론적으로 우선순위 큐는 힙 (Heap) 자료구조로 구현하게 되며 힙은 이진트리 (Binary Tree) 로 구현된다. 

 

• Priority Queue의 작동 

7, 1, 3, 5, 6 이 우선순위큐에 차례대로 입력될 경우

숫자가 높은 경우가 우선순위가 높다면

7, 6, 5, 3, 1 순으로 dequeue가 이루어진다.

 

즉 기준에 따라 dequeu 가 다르게 동작된다.

 

 

• 구현1 - List를 이용한 방법

만약 queue 와 같은 방식으로 메모리에 값이 시간 순으로 저장된다면 = List queue

 

dequeue할 때마다 우선순위가 높은 값을 찾는 과정이 있어야 한다. ( O(n) 소요 )

 

같은 과정을 모든 데이터가 dequeu() 될 때 까지 반복 

 

시간복잡도를 정리하자면

 

• 구현2 -  저장할 때마다 정렬

enqueue 할 때마다 정렬 (O(nlogn))

dequeue : 맨 앞에 있는 데이터 출력 ( O(1 ) 출력 후 뒤에 있는 데이터를 한 칸 씩 이동)

 

 

swap과 관련된 문제 : https://tmdtjs.tistory.com/16

 

• 구현3 - 완전 이진 트리

첫 번째 enqueue(n) 노드 하나 생성

두 번째 enqueue(n) 원래 노드의 left child 노드 생성

이후 우선순위가 높은 노드를 서로 swap

세 번째 enqueue(n) right chile 노드 생성

이후 마찬가지로  우선순위가 높은 노드를 서로 swap

 

계속적으로 left child 와 right child에 노드를 생성 후 우선순위가 높은 노드를 위쪽으로 root 노드 쪽으로 서로 swap 한다.

 

- 시간복잡도

 

enqueu() 

 

이진트리의 높이(logn)만큼 swap이 이루어져야한다. (worst case) 일 경우

O(logn) 

 

dequeu() 

 

root 노드 를 출력 후 마지막 노드를 root 노드로 바꾸어 준다.

이진트리의 높이(logn)만큼 swap이 이루어진다. (worst case) 일 경우

O(logn)

 

3가지 방법의 시간복잡도를 비교해보면 이진트리(Binary Tree)를 이용한 구현3이 가장 효율적이다.

 

이제는 Heap 자료구조를 이용할 것이다.

 

여기서 Heap이란 완전 이진 트리를 뜻한다. 

 

다음 시간에서는 Heap 자료 구조를 파악하며 Heap 자료구조를 이용하기만 하면 우선순위 큐를 이용할 수 있다는 점을 학습 할 것이다.