CH9-1 우선순위 큐의 이해(1)
9번째 챕터 강의를 시작하자. 제목이 우선순위 큐이다.
앞뒤가 열려있는 통의 구조를 생각하면 이게 큐인데… 우선순위 큐는 이름부터 어떤 큐와의 연관성이 있으리라고 생각할 수 있다.
그런데? 기본적인 모델은 유사해도 자료구조의 관점에서 큐의 특성,구현,내용,결과 등을 바라보면 큐와 우선순위 큐는 생각보다 관련이 없는 것 처럼 보이기도 한다. 따라서 너무 큐의 연장선상이라는 관점으로만 보지 마라.
8챕터에서 우리는 트리를 공부했다. 자료구조내부적으로 공부해야할 것을 생각해보면, 우선순위큐는 오히려 이 트리의 연장선상이라고 생각하는게 편하다.
큐같은 경우에는 선형자료구조이다. 그런데 우선순위큐는 비선형자료구조를 기반으로 한다. 이렇게보면 큐와 완전히 다른구조..
내용은 어렵지 않다. 이론적 이해를 위해 큐와 비교해보자.
우선순위 큐도 입구와 출구가 구분되어있다. 그리고 큐는 들어간 순서가 나가는 순서에 절대적인 영향을 미친다. 나가는 순서는 들어가는 순서에 의해 결정됨 그런데 우선순위큐는 들어간 순서와 나가는 순서가 관련이 없다. 그냥 입구 출구가 있어서 큐라고 할 뿐
그럼 어떻게 데이터를 뽑아내냐? 우선순위라는걸 따로 관리한다. 그리고 우선순위에 따라서 데이터를 뽑아낸다.
예를들어서, 데이터 a,b,c를 우선순위큐에 넣었다고 해보자. 그리고 뽑아내는 우선순위는 프로그래머가 결정한다.
데이터는, 그게 언제 들어갔든 간에 우선순위에 따라 나온다.
위와같은 특성을 가진 자료구조를 어떻게 구현할 것인가? 이게 우리 챕터의 주제이다.