[DataStructure] 우선순위 큐 (feat. 힙)

우선순위 큐 (feat. 힙)

---

1. 우선순위 큐

2. 힙

---

1. 우선순위 큐

큐(Queue)는 FIFO 형식으로 먼저 들어오는 데이터가 먼저 나가는 자료구조입니다.

우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

이는 힙(Heap)을 이용하여 구현합니다.

 

2. 힙

힙(Heap)은 완전이진트리 형태의 자료구조입니다.

부모 노드의 우선순위가 자식 노드의 우선순위보다 높게 유지됩니다.

 

부모 노드의 값이 자식 노드보다 항상 클 때는 최대 힙(Max Heap), 자식 노드의 값이 부모 노드보다 클 때에는 최소 힙(Min Heap)이라고 합니다. 최소 힙일 때는 자식 노드의 우선순위가 부모 노드의 우선순위보다 높아집니다.

 

- 삭제

1. 최대 힙일 때 루트노드 먼저 삭제합니다.

2. 가장 마지막 요소를 루트로 옮깁니다.

3. 우선순위가 높은 자식이 있다면 위치를 바꿉니다.

4. 우선순위가 높은 자식이 없을 때까지 반복합니다.

 

- 삽입

1. 마지막 위치에 새 요소를 삽입합니다.

2. 부모가 우선순위가 낮으면 부모와 자리를 바꿉니다.

3. 부모가 우선순위가 높을 때까지 반복합니다.

---

참고 사이트

[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)

 

우선순위 큐(Priority Queue)

 

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3