[자료구조] Priority Queue

윤석진·2022년 1월 4일
0
post-thumbnail

🚦 Priority Queue

우선순위를 가진 항목들을 저장하는

  • FIFO가 아니라 우선 순위가 높은 데이터가 먼저 나간다.

Priority Queue의 연산

  • insert
    우선순위 큐에 요소를 추가한다.
  • delete
    우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
  • find
    우선순위가 가장 높은 요소를 반환한다.
  • isEmpty
    우선순위 큐가 비어있는지 확인한다.

Priority Queue의 구분

  • 최소 우선순위 큐
  • 최대 우선순위 큐

Priority Queue의 응용 분야

  • 시뮬레이션 시스템
  • 네트워크 트래픽 제어
  • 운영 체제에서의 작업 스케쥴링

Priority Queue의 구현 방법

  • 배열(array)
  • 연결리스트(linked list)
  • 힙(heap)
구현 방법삽입삭제
순서 없는 배열O(1)O(n)
순서 없는 연결리스트O(1)O(n)
정렬된 배열O(n)O(1)
정렬된 연결리스트O(n)O(1)
O(log n)O(log n)
profile
공부하며 쓰는 블로그

0개의 댓글