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

우선순위 큐

우선순위 큐는 이름처럼 '큐'와 관련이 있다. 

앞서 공부한 큐의 핵심 연산 두 가지는 enqueue(큐에 데이터 삽입), dequeue(큐에 데이터 꺼내기)가 있었다. 마찬가지로 우선순위 큐의 핵심 연산도 enqueue(우선순위 큐에 데이터 삽입), dequeue(우선순위 큐에 데이터 꺼내기)이다.

 

하지만 큐와 우선순위는 연산의 결과에서 차이가 있는데,

 

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산 결과는 

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

** 우선순위 큐에서 중요한 것은 '우선순위'인데 그럼 우선 순위는 어떻게 결정 되는가? 

-> 프로그래머가 결정한다.

 

우선순위 큐의 구현 방법

1. 배열을 기반으로 구현하는 방법
2. 연결 리스트를 기반으로 구현하는 방법
3. 힙을 이용하는 방법

 

우선순위 큐를 구현하는 방법은 다음과 같다. 

 

배열을 사용했을 때 단점은,

1. 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다.

2. 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.(우선순위 낮은 데이터 저장시 최악)

 

연결리스트 사용시 단점은, 배열의 첫번째 단점은 갖지 않지만 두 번째 단점은 여전히 지닌다.

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

 

연결된 노드의 수가 많아지면, 많아진만큼 성능이 저하된다.

 

다라서 우선순위 큐는 단순배열도, 연결리스트도 아닌 '힙'이라는 자료구조를 이용해 구현한다.

 

힙

다음과 같은 조건을 만족할 때 '힙'이라고 한다.

1. 완전이진트리이다.
2. 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.
즉, 루트 노드에 저장된 값이 가장 커야 한다.(여기서 '값'은 말 그대로 '값'일수도 있고, 우선순위 큐에서 말하는 '우선순위'일수도 있다.)

 

**완전 이진트리 : 레벨 - 1 까지 포화상태이고 그 이후부터 왼쪽부터 꽉 찬 이진트리

 

최대 힙

최대 힙

 

위와 같이 루트 노드로 올라갈수록 저장된 값이 커지는 완전이진트리를 최대 힙(max heap)이라 한다.

 

 

 

최소 힙

최소 힙

 

반면에 위와 같이 루트 노드로 올라갈수록 저장된 값이 작아지는 완전이진트리를 최소 힙(min heap)이라 한다.

 

이렇듯 힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이니, 이를 기반으로 우선순위 큐를 간단히 구현할 수 있다. 

 

 

힙의 구현

힙의 구현은 곧 우선순위 큐의 완성으로 이어진다. (따라서 정확하진 않지만 힙과 우선순위 큐를 동일하게 인식하는 경향이 있다. 하지만, '힙' 자체는 우선순위 큐가 아니며 우선순위 큐를 구현할 수 있는 도구, 완전 이진 트리의 일종임을 기억하자.)

 

힙에서의 데이터 삽입과정

힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 알아야 한다. 먼저 데이터의 저장과정을 '최소 힙'을 기준으로 설명하겠다.

 

 

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

그럼 위 그림은 1. 완전 이진트리이고, 2. 자식 노드 데이터의 우선순위 <= 부모 노드 데이터의 우선순위  이므로 힙이 맞다.

 

위 상황에서 3을 저장한다고 가정해보자.

**저장한 이후에도 힙이어야 한다. 

 

데이터의 저장 전략은 다음과 같다. 

<힙 구현 알고리즘 - 데이터 삽입>
1. 우선순위를 고려하지 않고 넣을 데이터('3')을 완전이진트리가 깨지지 않을 '마지막 위치'에 저장
2. 부모노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 위치 교환(힙의 규칙에 맞을때까지 반복)

 

 

마지막 위치에 3 저장

부모 노드와 우선순위 비교 및 자리 바꿈

힙의 조건을 만족할때가지 반복해줌

제자리 찾음!

 

이로써 힙의 조건을 만족하며 숫자 3을 추가했다.

 

 

힙에서의 데이터 삭제과정

이번에는 데이터 삭제 과정을 알아보자. 우리는 우선순위 큐의 구현을 위해서 힙을 활용할 계획을 갖고 있다. 그런데 우선순위 큐의 삭제는 '가장 높은 우선순위의 데이터 삭제'를 의미하므로, 우리는 힙에서 루트노드를 어떻게 삭제할 것인지 고민해봐야 한다. 또한, 루트 노드 삭제 후에도 힙의 구조는 유지되어야 한다. 

 따라서 우리가 고민해야 할 문제는' 힙에서 루트 노드를 삭제한 다음에 ' 이 부분'을 어떻게 채우지?' 이다.

 

 

해결 전략은 다음과 같다

 

마지막 노드(완전 이진 트리에서 마지막 레벨 가장 오른쪽에 위치한 노드)를 루트 노드의 자리로 옮긴 후, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다.

 

즉, 데이터의 삭제 전략은 다음과 같다. 

<힙 구현 알고리즘 - 데이터 삭제>
1. 루트노드 삭제
2. 완전이진트리의 마지막 노드를 루트노드로 옮김
3. 자식 노드 중 우선순위가 높은 노드와 비교해서 위치를 교환(힙의 규칙에 맞을 때까지 반복)

 

루트노드 삭제 후 마지막 노드를 루트 노드로 이동시킨다.

자식 노드와 우선순위 비교 후 위치를 교환한다

위 과정을 반복해주면 제 자리를 찾아간다.

이런 형식으로 빈 공간을 채울 수 있다.

 

배열, 연결리스트, 힙 시간복잡도 비교

왜 우선순위 큐의 구현에 있어서 힙이 배열이나 연결리스트보다 좋은가?

배열 기반 데이터 저장의 시간 복잡도 : O(n)
배열 기반 데이터 삭제의 시간 복잡도 : O(1)

 

우선순위가 낮은 데이터를 배열에 저장하는 경우, 배열에 저장된 모든 데이터와의 우선순위 비교과정을 거쳐야 하기 때문,

삭제의 과정에서는, 맨 앞의 저장된 데이터를 삭제하면 되기 때문에 위와 같은 시간 복잡도가 나온다.

 

연결리스트 기반 데이터 저장의 시간 복잡도 : O(n)
연결리스트 기반 데이터 삭제의 시간 복잡도 : O(1)

 

연결리스트도 배열의 경우와 다르지 않다.

 

 

그러나 힙을 기반으로 하면 트리의 높이에 해당하는 수만큼만 비교연산을 진행하면 되기에 연산 수가 줄어든다.

 

힙 기반 데이터 저장의 시간 복잡도 : O(log2n) //밑이 2이고 진수가 n임
힙 기반 데이터 삭제의 시간 복잡도 : O(log2n)  //밑이 2이고 진수가 n임

 

힙은 완전 이진트리이므로 힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 떄마다 2배씩 증가한다.

따라서 데이터가 2배씩 늘 때마다 비교 연산의 횟수는 1회 증가하는 것이다.

이것이 힙을 사용하는 이유다.

 

 

(윤성우의 열혈 자료구조를 참고하여 작성하였습니다.)