[자료구조] 우선순위 큐란? (Priority Queue)

[자료구조] 우선순위 큐란? (Priority Queue)

등장배경

- 일반적인 큐에 대해서는, 데이터마다 레벨이 정해져있지 않았다. 즉, 우선순위가 정해져있지 않았다.

- 만약, 아래와 같이 줄 서 있는 사람들.. 생각

- 짧은 고객을 앞으로 보냄.

- 그럼 Average wait time per coustomer가 줄어듬.

순서를 다시 정렬함

위의 이유때문에, 우선순위 큐가 등장하였다.

큐 (Queue) 우선순위 큐 (Pirority Queue) 순서 시간 (먼저 넣은 것이 먼저 나감, FIFO) 데이터마다 레벨이 있느냐 없다. 있다.

의미

-

- 큐의 종류 중에 하나임.

- 우선순위 쿠의 구현은, Binary Heap(바이너리 힙, 이진 힙)을 이용하여 구현함.

큐 (Queue) 우선순위 큐 (Pirority Queue) 순서 시간 (먼저 넣은 것이 먼저 나감, FIFO) 데이터마다 레벨이 있느냐 없다. 있다.

Binary Heap

어레이로 구현하면, 손쉽고 빠르게 가능.

왼쪽(설계), 오른쪽(구현)

- Level-order traversal 레벨 별로 방문하는 것임.

- 자식과 부모의 규칙이 있다.

- i번쨰 노드의 자식은 2i와 2i+1에서 찾으면 된다. (리니어 어레이에서)

e.g) i가 4인 (i[4]의 자식은 i[8]과 i[9]임.

- 부모는 반대로 [i/2] (가우스함수) 쓰면 된다.

- 동작

- Entry min()

Return the entry at root

- Entry insert (key, value)

- Entry removeMin()

(미니멈 값을 찾아서 반환한뒤, 그 값을 지운다.)

- Remove entry at root

- Save for return value

-

중요한 사실

1) a는 컴플릿 바이너리 트리여야함

2) key값, 부모는 자식보다 작아야함.

- Insert할 때 동작들

insert 안에서는 버블업함. "heap-order property"를 만족하기 위해서

- RemoveMin9)

가장 끝에있는 노드를, 젤 위에 놓음.

1) 그 이유는 a Complete BT를 유지하기 위해서.

- 배열로 생각해봐도, 끝에있는 값을 가장 첫번쨰로 갖다 놓는 게, 자연스럽다.

2) key값조정

올려놓았으면 서브트리와의 관계를 이용한다.

Complexity

Searh Insert Remove Max/Min Array (unsorted) O(n) O(1) O(n) O(n) Array (sorted) O(log2n) O(n) O(n) O(1) Linked List O(n) O(1) O(n) O(n) Binary Heap O(log2n) O(log2n) O(log2n) O(1)

코드

인용/참고자료

한양대학교 - 데이터 구조론 (우선순위 큐)

http://www.kocw.net/home/cview.do?cid=ec066a0f24e13e9a

from http://i5i5.tistory.com/558 by ccl(A) rewrite - 2021-10-17 01:27:00