priority queue(binary heap)

1. concepts>

☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조'

 

☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용

ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

 

자료구조	추출되는 데이터
stack	가장 나중에 삽입된 데이터
queue	가장 먼저 삽입된 데이터
priority queue	가장 우선순위가 높은 데이터

 

☝️ 우선순위 큐는 크게 두 가지 방법으로 구현 가능

① 단순히 list로 구현

② heap을 이용하여 구현

 

※ heap을 사용해서, 단순히 먼저 들어오거나 나중에 들어온 순서가 아닌,

우선순위가 높은, 즉 최댓값 먼저, 아니면 최솟값 먼저 뽑을 수 있는 자료구조를 이용해 효율적인 시간 효율 내로 연산 진행이 가능하다. ※

 

☝️ 구현 방식에 따른 구현 시간 복잡도 비교 (데이터 개수 N)

우선순위 큐 구현 방식	삽입 시간	삭제 시간
list	O(1)	O(N)
heap	O(logN)	O(logN)

① list의 경우 삽입은 단순히 뒤쪽에 삽입하면 되므로 O(1)이지만, 삭제한다면 우선순위가 높은 데이터를 찾아야 하므로 O(N)의 시간이 걸림

② heap의 경우 삽입과 삭제 모두 최악의 경우에도 O(logN)을 보장한다

 

※ 여기서, heap에 N개의 데이터를 넣었다가 모두 꺼내는 작업은 힙 정렬과 동일 (시간 복잡도는 O(NlogN))
(일반적으로 사용되는 정렬 알고리즘과 마찬가지로 정렬로 사용된다)

2. heap 요약>

★ binary heap에 관한 자세한 정보는 아래 하단 포스팅 꼭 참조! ★

Binary heap

☝️ heapq python library를 사용하자면,

 

→ find max()는 list의 indexing 사용 후, heapify() 함수 사용
(또는 heappop()을 사용하면 알아서 최상단 node를 빼주고, heapify()까지 진행)

 

→ insertion은 heappush() 사용 (알아서 max 또는 min heap 형성)

 

→ heapsort()는 별도 정렬 포스팅 참조 (heappush()와 heappop()을 여러 번 쓰면 된다)

3. priority queue 백준 문제>

** 추후 추가 예정

---

* 출처1) 이코테 2021 https://youtu.be/AjFlp951nz0

* 출처2) heap 소개 유투브 https://youtu.be/Zl07LUsR6P0

* 출처3) heap 총정리 youtube https://youtu.be/TK48r1Dlo4k

* 출처4) heap wiki https://en.wikipedia.org/wiki/Heap_(data_structure) 

* 썸네일 출처) https://www.vectorstock.com/royalty-free-vector/priority-queue-concept-icon-luxury-class-flight-vector-39920837

* 스택오버플로우 출처) https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity