(1) 프롤로그
큐는 먼저 들어간 것이 먼저 나오는 자료구조임을 우리는 이미 알고 있고
보통 우선 순위 큐를 공부할 때 이와 연결하려는 경향이 있으나
사실은 큐 보다는 트리의 연장선상에 있는 것이 우선 순위 큐이다.
(2) 우선순위 큐란?
들어가는 순서대로 나가는 것이 큐라면,
들어가는 순서와 나가는 순서가 아무 관련이 없는 것이 우선 순위 큐이다.
뽑아내는 근거는 들어오는 순서가 아닌 우선순위
입구와 출구가 달라서 '큐'라는 이름이 붙은거지, 나머지는 큐와 유사성이 없다.
개념은 간단하다.
그러나 우선순위 큐는 개념보다 구현에 초점이 맞추어져서 논의되는 주제이다.
우선순위 큐에도 enqueue와 dequeue 연산이 있으나 우선순위 큐의 dequeue연산은 들어간 순서에 상관없이 우선순위를 근거로 한다.
데이터 별 우선순위의 비교기준은 프로그래머가 결정할 몫이다. 따라서 우선순위 큐 자료구조를 활용하는 프로그래머가 직접 우선순위 비교기준을 결정할 수 있도록 구현이 되어야 한다.
(3) 우선 순위 큐의 구현 방법
- 배열을 기반으로 구현하는 방법
- 연결 리스트를 기반으로 구현하는 방법
- 힙(heap)을 기반으로 구현하는 방법
의 세가지가 있는데
공부와 상관없이 구현해야하는데 data가 기껏해야 4,50개라면 배열,연결리스트를 기반으로 구현해도 된다.
하지만 그렇게 하면 자료구조의 공부 목적에서 멀어진다.
일단 배열, 연결리스트를 기반으로 한 구현이 간단한 이유를 알아보면
우선순위대로 리스트에 데이터를 저장하면 끝이기 때문이다.
예시로 배열기반으로 우선 순위 큐를 구현하고 이 때 데이터는 정수, 정렬기준은 오름차순이라 가정해보자.
x를 삽입한다 가정, 현재 배열이 오름차순 정렬되어 있으면 x보다 작은 수 A, x보다 큰 수 B가 붙어 있으면 B이상의 숫자들을 모두 한칸씩 미루고 원래 B의 자리에 x를 삽입하면 된다.
그런데 이렇게 하면
worst case의 경우 n+1번째 수를 삽입할 때 n개를 모두 검사하고 n+1번째 배열에 수를 삽입해야 하고
best case의 경우에도 n개의 수를 모두 1칸씩 미뤄야 하므로
검사 또는 배열의 성분의 위치를 바꾸는 연산이 n(n+1)/2 회 일어난다.
즉 연산의 시간복잡도가 n제곱에 비례한다.
그럼 연결리스트일 때는 달라지는가?
연결리스트일 때는 데이터의 best case일 때 배열과 같이 모든 수를 한칸씩 이동시키는 과정이 없으므로 좀 더 나아지나 여전히 시간복잡도는 n제곱에 비례한다.
그리고 배열은 비교연산시 access가 좀 더 편하나 연결리스트 기반으로 구현할시는 주소를 타고 넘어가고 넘어가므로 좀더 시간이 많이 걸린다.
(malloc역시 배열을 선언하는 것보다 시간이 좀더 걸린다.)
그래서 등장한 것이 힙(heap)이라는 자료구조이다.
(4) 힙의 소개
힙은 이진 트리의 일종인데 완전이진트리라는 것에까지 관심을 가지는게 중요하다.
-
힙은 루트 노드에 저장된 값이 가장 크다.
즉, 우선순위가 가장 큰 값이 루트 노드에 저장된다. -
모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같다.
1,2를 만족하는 완전이진트리를 최대힙이라 하는데 이는 삽입할 때도 나름의 장점이 있다.
1,2를 반대로 하여 최소힙이라는 것을 만들 수도 있다.
최대힙을 보면 1,2만 만족하면 되므로 같은 레벨 사이의 대소관계에 따른 규칙은 따로 없다.
ex.위의 그림에서 Level2에 있는 100 90 80 120
