[자료구조] 우선순위 큐 (priority queue)

우선순위 큐

• 우선순위 큐의 정의
• 우선순위 큐의 구현
• Heap
  • Heap의 정의
  • Heap의 구현
  • Heap에서의 insert / delete (Up-Heap, Down-Heap)
• 우선순위 큐의 사용 예시

 

---

우선순위 큐란?

• 스택? LIFO - 가장 마지막에 삽입된 원소가 가장 먼저 추출된다
• 큐? FIFO - 가장 먼저 삽입된 원소가 가장 먼저 추출된다
• 우선순위 큐?
  • 큐와 달리, 각 item들이 우선순위를 가지고 있다.
  • 높은 우선순위를 가진 item들이 가장 먼저 추출된다.
    • 값이 클수록 높은 우선순위를 가진다면, 큰 값부터 추출
    • 값이 작을수록 높은 우선순위를 가진다면, 작은 값부터 추출
  • 구현
    • 1) 우선순위에 따라 정렬되어 있는 경우
      • delete는 빠르지만, insert는 느리다
    • 2) 우선순위에 따라 정렬되어 있지 않은 경우
      • insert는 빠르지만, delete는 느리다.

---

우선순위 큐의 구현?

구현	insert	delete	find high priority
BST (binary searcg tree)	평균 O(logN)	평균 O(logN)	평균 O(logN)
AVL Tree	O(logN)	O(logN)	O(logN)
binary heap	O(logN)	O(logN)	O(1)
ordered list	O(N)	O(1)	O(1)
unordered list	O(1)	O(N)	O(N)

(표 : dongchans.github.io/2019/29/ )

 

• binary search tree를 사용하게 되면 왜 안 좋은가?
  • 작을수록 우선순위가 크다고 했을 때,
  • priority queue에서 하나씩 제거하면 왼쪽에 존재하는 item이 계속 제거된다.
  • 따라서 오른쪽으로 긴 모양의 tree가 되기 때문에 delete가 O(n)에 가깝게 되기 때문이다.
  • +) 위의 도표에서도 "평균" O(logN)이라고 표기한 이유

• bineary heap을 통해서 우선순위 큐를 구현할 때 성능이 가장 좋다.

---

 

---

우선순위 큐의 사용?

• 다익스트라 알고리즘 : 최단거리 찾는 문제
• 균일비용탐색, 최상우선탐색, A* 알고리즘