Priority Queue

Queue

• FIFO 형식의 자료구조
• 입력된 순서대로 처리하기 위해 사용

Priority queue

• 데이터의 우선순위가 존재하는 자료구조
• 우선순위가 높은 데이터부터 나옴

Heap

• Complete Binary tree로 구현된 자료구조

Priority Queue를 구현하기 위한 방식은 여러가지가 있지만, 힙을 통한 구현이 예제가 많다.

Max Heap 과 Min heap

max heap
부모노드의 값이 자식 노드의 값보다 크거나 같다.

min heap
부모 노드의 값이 자식 노드의 값보다 작거나 같다.

어디에 쓸까?

운영체제 작업스케줄링, 정렬, 네트워크 관리에 이용

어떻게 구현할까?

max heap 기준

삽입
1. 마지막 노드에 삽입할 값을 넣는다.
2. 해당 값을 해당 값의 부모 노드와 값을 비교한다.
3. 부모 노드의 값이 더 작을 경우 위치를 바꿔준다.

부모노드의 인덱스: Complete binary tree이기 때문에 부모노드의 인덱스는 (index - 1)/2

삭제
1. 루트 노트 삭제
2. 마지막 인덱스를 루트노드의 넣는다.
3. 자식 노드 중에 작은 노드 값과 위치를 바꾸며 재정렬한다.