ki hyun's 개발블로그

힙에 관하여 이전 포스트에서 힙을 이용한 정렬인 힙 정렬에 대해 소개했다. 힙 정렬은 분명 훌륭한 알고리즘이지만 사실 나중에 소개할 퀵 정렬을 잘 구현하는 것이 일반적으로는 더 빠르다. 하지만 힙은 여러 방면으로 유용하게 사용할 수 있는데 이번 포스트에서는 힙을 가장 잘 응용하여 널리 쓰이고 있는 우선순위 큐를 소개해보려고 한다. 우선순위 큐 키라는 값을 가진 원소들을 다루기 위한 자료구조 보통의 큐는 FIFO를 구현한다. 따라서 우선순위에 상관없이 무조건 먼저 들어온 원소가 가장 먼저 나간다. 하지만 우선순위 큐에서는 우선순위에 따라 나가는 순서가 결정된다. 가장 나중에 들어온 원소이더라도 우선순위가 가장 높다면 가장 먼저 나가게 되는 것이다. 우선순위 큐의 종류 힙과 같이 우선순위 큐에도 최대 우선순..