우선순위 큐

Heap에 대해 배운다면서 갑자기 웬 큐를, 그것도 우선순위 큐라는 특이한게 나와서 당황했다. 하지만 Heap은 우선순위를 가진 항목들을 저장하는 우선순위 큐를 구현하기 위해 필요한 자료구조이다. 기존의 큐는 FIFO(선입선출) 이었지만, 우선순위 큐는 우선 순위가 높은 항목을 먼저 내보내게 된다.

• 스택/FIFO큐와의 차이점은 당연히 삭제되는 요소가 무엇이냐 이다.
• 어떤 값을 우선순위로 두느냐에 따라 최소/최대 우선순위 큐로 구분한다.

ADT

• create(): 우선순위 큐 생성
• init(q): q를 초기화
• is_empty(q): q의 공백체크
• is_full(q): q의 포화체크
• insert(q, x): q에 요소 x 추가
• delete(q): 가장 우선순위가 높은 요소를 삭제하고 반환
• find(q): 가장 우선순위가 높은 요소를 반환

구현 방법

1. Array (맨 뒤에 있는 값이 항상 제일 크게/작게)
2. LinkedList (head 포인터에 있는 값이 항상 제일 크게/작게)
3. Heap

• 구현방법 별 삽입/삭제 시간복잡도

  Expression	Insertion	Deletion
  순서 없는 배열	O(1)	O(n)
  순서 없는 연결 리스트	O(1)	O(n)
  정렬된 배열	O(n)	O(1)
  정렬된 연결 리스트	O(n)	O(1)
  heap	O($log_2n$)	O($log_2n$)