Priority Queue & Heap

PQ란?

• 보통 queue와 비슷하게 동작하고 queue 안의 element들이 특정 순위(priority)를 가지는 Abstract Data Type
• priority에 의해 PQ에서 제거되는 순서가 결정된다.
• PQ는 오직 comparable data만 사용할 수 있다. ( 어떤 방식으로든 원소들의 순서를 정해줄 수 있어야한다. )
• priority가 무작위인 원소들이 들어있는 PQ에서 항상 순서대로 뽑는방법은?
  -> POLL하기 직전마다 sort를 한다? -> 너무 비효율적
  => HEAP을 사용한다.

Heap이란?

• heap invariant를 만족하는 트리 기반 자료구조
• heap invariant란 Each node in a tree has a key which is more extreme (greater or less) than or equal to the key of its parent
• MAX Heap : 부모가 큼 / MIN Heap : 부모가 작음

  PQ == Heap?
  아니다
  PQ는 ADT이므로 HEAP이 아닌 다른 자료구조를 이용하여 만들 수 있다.

Complexity PQ with Binary Heap

• Binary Heap Construction O(n)
• Polling O(logn)
• Peeking O(1)
• Adding O(logn)
• Naive Removing O(n)
• removing with hash table O(logn)
• Naive contains O(n)
• contains with hash table O(1)

Min PQ -> MAX PQ

• 보통 MIN or MAX PQ를 제공하므로 바꾸는 법 필요

• 1) number 비교일 경우
  -를 붙여주면 됨
  ( 1,2,3 -> -1,-2,-3 으로 변환 하면 -3,-2,-1 순으로 poll 되므로 마지막에 - 붙여주면 min pq -> max pq)

• 2) string 비교일 경우
  보통 lex comparator을 사용해 사전순으로 비교한 결과를 양수 음수 0 으로 return하여 sort함
  이 결과값에 - 붙여주면 반대로 pq로 사용 가능
  양수 -> 음수 / 0 -> 0 / 음수 -> 양수