약한 정렬

16장 힙으로 우선순위 유지하기

힙은 데이터 세트에서 가장 큰, 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다. 힙의 기능을 제대로 파악하기 위해 지금까지 보지 못했던 새로운 자료 구조인 우선순위 큐부터 살펴보자. 1. 우선순위 큐 9.5장에서 배웠던 큐는 FIFO 방식으로 항목을 처리하는 리스트였다. 근본적으로 큐 끝에서만 데이터를 삽입하고 큐 앞에서만 접근과 삭제를 수행한다. 큐의 데이터에 접근하려면 데이터가 삽입됐던 순서를 따라야 한다. 우선순위 큐(Priority Queue)는 삭제와 접근에 있어 전형적인 큐와 흡사하나 삽입에 있어 정렬된 배열과 비슷한 리스트다. 즉 우선순위 큐 앞에서만 데이터에 접근하고 삭제하되 데이터를 삽입할 때는 데이터를 늘 특정 순서대로 정렬시킨다. 우선순위 큐는 추상 데이터 타입의 ..