우선 순위 큐 관련 솔루션

[1. 개요]

우선 순위 큐(=편의 상 힙으로 표기) 는 정렬 상 우선순위가 높은 원소를 먼저 꺼낼 수 있는 큐이다.

• 최대 힙
• 최소 힙

힙을 대상으로 하는 push 와 pop 모두 O(logn) 으로 동작한다.

 

힙 내부 데이터 변경으로 인해 heapify 가 필요할 수도 있지만, 이런 경우에 자주 없다.

• 다익스트라에서 특정 노드에 대한 가중치가 바뀌는 경우가 대표적이지만,
• 이 때에는 힙에 다시 푸쉬하는 편이 더 간단하다.
• heapify 는 보통 O(n) 으로 동작하여 다소 느려, 오히려 더 안 좋을 수 있다(?).

보통의 문제는 크게 최대 힙, 최소 힙 둘 중 하나만 사용하는 경우가 다수이지만,

두 가지 힙 모두 사용하여 풀어야 하는 문제도 간혹 존재한다.

• 대표적으로 Running median 같은 문제

대부분의 언어에서 힙이라는 자료구조를 표준 라이브러리로 제공하나,

자료형이 int, string 같은 것이 아닌 custom 객체라면, 정렬 기준을 제시하는 방법을 알아야 한다.

• 여기에 링크...

[2. 예제]

• https://testkernelv2.tistory.com/480
• https://testkernelv2.tistory.com/551
• https://testkernelv2.tistory.com/554
• https://testkernelv2.tistory.com/557
• e
• f
• g
• h
•