[자료구조] 우선순위 큐와 힙

오늘은 우선순위 큐에 대해서 말해보려고 합니다.

[관련 알고리즘 문제]

2019/02/17 - [알고리즘 문제/알고스팟] - [알고스팟 RUNNINGMEDIAN] 변화하는 중간값

우선 일반적인 큐의 특성에 대해 설명하자면 먼저 들어간 데이터가 먼저 나옵니다.

반면 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

그럼 여기서 궁금한 점이, 우선순위 큐에 저장되는 모든 데이터들은 각자 우선순위를 나타내는 값을 지녀야하는

것일까요? 꼭 그렇지는 않습니다. 우선순위를 지녀야한다기 보다는, 데이터를 근거로 우선순위를 판단할 수 있어야

 합니다.

[우선순위 큐 구현방법]

1. 배열을 기반으로 구현하는 방법

2. 연결 리스트를 기반으로 구현하는 방법

3. 힙(heap)을 이용하는 방법

[배열로 구현하는 경우]

1. 배열의 가장 큰 단점인 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로

당겨야 한다.

2. 삽입의 위치를 찾기 위해, 저장된 모든 데이터와 우선순위 비교를 진행할 경우가 생긴다.

[연결 리스트로 구현하는 경우]

1. 배열과 같이 데이터를 삽입 및 삭제하는 과정에서 데이터를 앞뒤로 이동시키는 일은 없다.

2. 삽입의 위치를 찾기 위해, 첫 번째 노드부터 시작해서 마지막 노드에 저장된 데이터와 우선순위 비교를 진행할

경우가 생긴다.

힙(heap)이란?

1. 힙은 '이진 트리'이되 '완전 이진 트리'이다.

2. 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야한다.

즉, 루트 노드에 저장된 값이 가장 커야 한다. 여기서 말하는 '값은' 데이터 그 자체를 의미할 수 도 있고

'우선순위'가 될 수 도 있다.

위의 문장에서 말하는 형태로 트리를 그려보면 아래와 같이 표현할 수 있다.

왼쪽 그림처럼 루트노드로 올라갈수록 데이터가 커지는 '완전 이진 트리'를 가리켜 '최대 힙'이라고 하고 오른쪽

그림처럼 루트노드로 올라갈수록 값이 작아지는 '완전 이진 트리'를 가리켜 '최소 힙'이라고 한다.

이렇듯, 힙은 프로그래머가 정의한 우선순위에 따라 가장 우선순위가 높은 데이터를 루트 노드에 저장할 수 있는

자료구조이다.

[힙에서의 데이터 저장 과정]

힙의 구현을 위해서는 우선적으로, 데이터가 저장되는 방법을 알아야 한다. 따라서 데이터의 저장과정을

'최소 힙'을 기준으로 설명하겠다.

위 그림에 쓰여진 숫자를 데이터 겸 우선순위라 가정하고, 숫자가 작을수록 우선순위가 높다고 가정하자.

그렇다면 위의 그림은 힙이 맞다.

그 이유는

1. 완전 이진트리이다.

2. 어느 위치에서든 다음과 같은 식이 성립한다.

자식 노드의 데이터 우선순위 <= 부모 노드의 데이터 우선순위

새로운 데이터를 저장하기 위해서는 위와 같이 정의한 '우선 순위'에 따라 저장되어야 한다. 

이를 위해선 다음과 같은 과정을 통해 데이터를 저장한다.

1) 새로운 데이터가 우선순위가 제일 낮다고 가정하에 가장 '마지막 위치'에 저장한다.

여기서 말하는 마지막 위치란, 마지막 레벨의 가장 오른쪽 위치를 뜻한다.

2) 부모 노드의 우선순위를 비교하여 위치를 바꿔야한다면 바꿔준다.

3) 바뀐 다음에도 계속해서 다음 부모 노드와 비교한다.

4) 우선순위에 맞는 위치를 찾을때까지 1~3번 과정을 반복한다.

그럼, 힙에 숫자 3을 추가하는 과정을 살펴보자.

[추가 과정 1/3]

위 그림과 같이 숫자 3을 맨 마지막 노드에 추가하고, 그 부모 노드인 8과 우선순위를 비교한다.

3의 우선순위가 더 높으므로, 8과 자리를 바꿔준다.

[추가 과정 2/3]

우선 순위에 따라 3과 8의 위치를 바꾼 후, 현재 3의 위치의 부모 노드인 4와 우선순위를 비교한다.

3의 우선순위가 더 높으므로, 4와 자리를 바꿔준다.

[추가 과정 3/3]

우선 순위에 따라 3과 4의 위치를 바꾼 후, 현재 3의 위치의 부모 노드인 1과 우선순위를 비교한다.

이번에는 부모노드의 우선순위가 더 높으므로 더 이상 자리를 바꿔주지 않는다.

즉, 3은 우선순위에 따른 자신의 위치를 찾은 것이다.

반면, 힙에서의 데이터 삭제 과정은 어떻게 될까?

먼저 우선순위 큐의 데이터 삭제는 우선순위가 가장 높은 데이터를 삭제하는 것이므로 루트노드를 삭제한다고

생각하면 된다.

물론, 데이터 저장과 마찬가지로 데이터를 삭제한 이후에도 힙의 구조를 유지해야한다.

이를 위해선 다음과 같은 과정을 통해 데이터를 저장한다.

1) 마지막 노드를 루트 노드로 위치시킨다.

2) 루트 노드를 우선순위에 따라 자식 노드와의 비교를 통해 자리를 바꿔준다.

3) 바뀐 다음에도 계속해서 다음 자식 노드와 비교한다.

4) 우선순위에 맞는 위치를 찾을때까지 1~3번 과정을 반복한다.

루트노드의 데이터를 삭제하는 것은 다음 그림과 같다.

루트 노드를 삭제한 후, 가장 마지막에 있는 노드를 루트 노드로 위치시키면서 우선순위를 비교한다.

[삭제 과정 1/3]

맨 마지막 노드 8을 루트 노드로 이동시킨다.

[삭제 과정 2/3]

루트 노드와 자식 노드들 사이의 우선순위를 비교한다. 만약 루드 노드의 우선순위가 자식 노드들보다 높다면

위치를 제대로 찾은 것이겠지만 그림과 같이 자식 노드들의 우선순위가 더 높다면 자리를 바꿔줘야한다.

모든 자식노드들이 루트 노드보다 우선순위가 높을 경우, 자식노드들간의 우선순위를 비교하여

더 높은 우선순위를 가진 노드와 자리를 바꾼다.

그림에서는 3의 우선순위가 7보다 높기 때문에 8과 3의 자리를 바꾼다.

[삭제 과정 3/3]

마찬가지로 8과 4의 우선순위를 비교하여 자리를 바꿔준다.

[삭제 과정 완료]

[우선순위 큐의 성능 평가]

1. 배열 기반, 연결 리스트 기반의 우선순위 큐

1) 데이터 저장의 시간 복잡도 : O(n)

우선순위가 낮은 데이터를 저장하는 경우 배열의 모든 데이터와 비교를 진행하는 경우, O(n)만큼 걸린다.

2) 데이터 삭제의 시간 복잡도 : O(1)

삭제의 과정에서는 맨 앞에 있는 데이터(우선순위가 가장 높은)를 삭제하기 때문에 O(1)만큼의

시간이 걸린다.

2. 힙 기반의 우선순위 큐

1) 데이터 저장의 시간 복잡도 : O(logN)

2) 데이터 삭제의 시간 복잡도 : O(logN)

힙은 완전 이진트리이므로 힙에 저장할 수 있는 데이터의 수는 트리의 높이가 1씩 커질 때마다 두 배씩 증가한다.

그렇기 때문에 데이터의 수가 2배 늘어날 때 마다, 비교 연산 횟수는 1씩 증가한다.