[자료구조 및 프로그래밍] 11. 우선순위 큐와 Heap

우선순위 큐

우선순위 큐는 우선순위를 가지는 아이템들을 가지는 큐이다.

일반적인 큐와 마찬가지로 push(), pop() 두가지 기능을 제공하지만, 우선순위 큐는 데이터를 저장할 때 단순히 데이터의 값 뿐만 아니라 데이터의 우선순위를 같이 저장하는 점이 다르다.

 

그래서 우선순위 큐에는 push(x, p) 와 같은 형태로 데이터를 저장한다.

x 는 저장하는 데이터, p 는 저장하는 데이터의 우선순위이다.

그리고 pop을 할 때는 우선순위가 높은 데이터부터 나온다.

우선순위 큐의 구현

우선순위 큐의 개념은 간단하다.

그런데 우선순위 큐의 구현은 간단하지 않다.

 

만약 일반적인 큐를 구현할 때처럼 연결 리스트를 사용한다면 어떨까?

데이터를 pop 할 때, 우선순위가 높은 순부터 뽑아야 하므로 아래 2가지 방법중 하나를 사용할 수 밖에 없을 것이다.

 

1. 일단 맨 뒤에 push 한다. 나중에 pop 할 때는 연결 리스트 전체를 순회하면서 우선순위가 제일 높은 값을 찾아 반환한다.

2. 큐에 데이터를 넣을 때 우선순위에 맞게 정렬된 상태를 유지하도록  push 한다. pop을 할 때는 제일 앞의 값을 pop 한다.

 

1번 방법을 사용한다면 push 하는데 O(1) 의 시간이 걸린다.

하지만 pop을 하는데 최악의 경우 O(n)의 시간이 걸린다.

우선순위가 높은 값이 하필 맨 뒤에 있을 수도 있기 때문이다.

 

2번 방법을 사용한다면 최악의 경우 push 하는데 O(n) 의 시간이 걸린다.

새로 넣을 데이터가 들어갈 위치를 순회하며 찾아야 하는데, 새로 넣을 데이터가 제일 크다면 모든 값을 순회해야 하기 때문이다.

pop을 하는데는 언제나 O(1) 의 시간이 걸린다.

 

즉, 이렇게 구현하면 push 하거나 pop을 할 때 현재 우선순위 큐에 들어있는 원소 개수에 비례하는 시간이 걸린다.

만약 n번의 push 연산 이후, n번의 pop 연산을 수행한다면 최악의 경우 O(n^2) 의 시간이 걸릴 것이다.

 

이를 해결하기 위해서는 좀 더 효율적으로 데이터를 넣고 뺄 수 있는 새로운 자료구조가 필요하다.

효율적인 우선순위 큐는 운영체제의 프로세스 스케줄링이나 다익스트라 알고리즘과 같은 곳에서 사용되므로 아주 중요하다.

---

완전 이진 트리

우선순위 큐를 더 효율적으로 구현하게 해줄 새로운 자료구조를 정리하기에 앞서,

이전 글에서 정리했던 '이진트리'에 대해 좀 더 정리해보자.

 

height 가 h인 이진 트리가 하나 있다.

height 가 h 이므로 이 이진트리에는 depth가 0인 노드부터 h인 노드가 모두 존재한다.

이때 depth 가 d 인 노드는 이진트리에 최대 2^d 개 존재할 수 있다.

 

만약 이진 트리의 모든 각각의 level 에서 들어갈 수 있는 최대 개수의 노드를 가지고 있다면 이를 '가득찼다' 라고 표현할 수 있다.

만약 height = h 인 이진트리가 가득 찼다면, 이 이진트리에는 총 2^(h+1) - 1 개의 노드가 존재한다.

 

2^0 + 2^1 + 2^2 + ... + 2^h = 2^(h+1) - 1

 

높이가 2인 가득찬 이진 트리

 

다시 height 가 h 인 이진 트리를 하나 생각해보자.

이 이진 트리의 h-1 번째 레벨까지는 들어갈 수 있는 모든 노드로 꽉 채워져 있고, 제일 깊은 depth 인 h 에서는 제일 왼쪽부터 노드가 채워져 있다고 해보자.

높이가 3인 완전 이진 트리

 

이렇게 depth = 2 까지는 모든 노드가 채워져있고,

그 다음 마지막 depth인 3에서는 왼쪽부터 노드가 채워진 형태의 이진 트리를 '완전 이진 트리' 라고 한다.

그리고 노드 n 개로 구성된 완전 이진 트리의 높이 height 는 언제나 log(n) 의 내림이다.

 

그리고 이런 특성에 기반하여, 우리는 위 이미지와 같이 각 노드에 '번호' 를 매겨줄 수 있다.

이렇게 노드에 번호를 매기게 되면, 번호만 가지고 이진트리에서 노드의 위치를 역으로 추정할 수 있게 된다.

따라서 이진트리를 1차원 배열을 통해 표현할 수 있게 된다.

 

이 경우에 사용하는 배열은 인덱스 1부터 시작하는 one-off addressing 을 사용해야 한다.

인덱스를 통해 부모, 왼쪽 자식 노드, 오른쪽 자식 노드를 아래와 같이 표현할 수 있다.

 

어떤 노드의 번호가 i 라면

왼쪽 자식 노드의 번호는 i * 2

오른쪽 자식 노드의 번호는 i * 2 + 1

부모 노드의 번호는 i / 2 의 내림

 

이를 이용하면 기존에 사용하던 많은 이진트리 연산을 연결 리스트가 아닌 배열을 통해 처리할 수 있다.

그리고 이렇게 인덱스의 값을 이용하여 연산을 수행하면 컴퓨터 입장에서도 꽤 효율적으로 연산을 할 수 있게 되는데,

2를 곱하고 나누는 것은 컴퓨터 입장에서 비트를 하나 좌/우로 옮기는 것과 같기 때문이다.

 

만약 우리가 흔히 사용하는 0-주소 방식을 사용하게 되면 위 방식을 그대로 사용할 수 없다.

i = 0 일 때 아무리 2를 곱해도 여전히 0 이므로 왼쪽 자식 노드를 표현할 수 없기 때문이다.

이 경우에는 i 에 1을 더해주는 방식을 취해야 하며, 이는 결국 1-주소 방식과 동일하다.

 

이를 이용하여 1277번째 노드의 depth는 몇인지 계산해보자.

depth 가 d 인 노드들이 가질 수 있는 번호의 범위는 2^d ~ 2^(d+1) -1 이다.

1277 보다 작은 2의 거듭제곱 수 중 제일 큰 수는 1024 이다.

따라서 1277은 2^10 ~ 2^11 - 1 사이 범위에 있으므로, 1277의 depth 는 10이다.

---

Heap

이제부터 어떤 완전 이진트리 A에 대해 A(i) 를 i번째 노드의 값이라고 하자.

(A[i] 라고 하면 0-인덱스 기준의 배열과 혼동하기 쉽기 때문에 노테이션을 별도 정의 하였다.)

 

만약 어떤 완전 이진트리 A 에 대해 다음을 만족한다면, 이 이진트리는 heap property 를 만족한다고 하고,

이 이진트리를 Heap 이라고 부를 수 있다.

 

A(parent(i)) >= A(i)

 

즉 부모 노드의 값이 자식 노드의 값보다 크거나 같은 상황이다.

특히, 이렇게 부모 노드의 값이 자식 노드의 값보다 크거나 같은 경우를 Max-Heap 이라고 하며,

반대로 부모 노드의 값이 자식 노드의 값보다 작거나 같은 경우를 Min-Heap 이라고 한다.

 

 

위와 같은 모습이 Max Heap 의 한 예시이다.

Heap Operatioins

자료구조로서 힙을 생각할 때는 아래와 같은 연산도 같이 고려한다.

 

Heapify(A, i) : A의 i번째 노드가 Heap 특성을 만족하도록 만든다. O(log n) 시간이 걸린다.

Build-Heap() : 무작위 배열을 Heap으로 만든다. O(n) 의 시간이 걸린다.

Inesrt(A, key) : A 라는 힙에 새로운 값 key 를 추가한다. O(log n) 시간이 걸린다.

Extract(A) : A 라는 힙에서 제일 앞의 값을 뺀다. O(log n) 시간이 걸린다.

 

이 중에서 Heapify 와 Build--Heap 보다는 자료구조로서 Insert, Extract 을 자세히 정리하려고 한다.

이 글의 서두에서 말했던 우선순위 큐의 효율적인 연산을 위해 이 Heap 자료구조를 사용하는데,

우선순위 큐의 Push, Pop 이 Heap의 Insert, Extract 와 관련되어 있기 때문이다.

Insert

먼저 Heap 에 새로운 데이터를 추가하는 경우를 생각해보자. (Heap은 Max-Heap 으로 생각하여 정리한다.)

위 이미지와 같은 heap 에 새로운 데이터 11을 추가한다고 해보자.

 

데이터의  추가는 아래와 같은 순서로 진행된다.

 

1. 11을 완전 이진트리 맨 마지막에 추가한다.

(즉, 배열에서 비어있는 인덱스 중 제일 작은 인덱스에 값을 추가한다.)

 

 

그러면 그림과 같은 상태가 된다.

 

2. 새로 추가된 11과 그의 부모노드의 값을 비교한다.

만약 새로 추가된 노드의 값이 부모노드의 값보다 크거나 같다면, 서로 위치를 바꾼다. (swap)

 

 

그림과 같은 상태가 된다.

 

3. 다시 새로 추가된 11과 그의 부모 노드 값을 비교한다.

새로 추가된 노드가 부모 노드보다 작아서 위치가 바뀌지 않을때까지 반복한다.

위 그림과 같이 더 이상 교환이 이루어질 수 없으므로 11의 위치가 정해졌다.

 

최악의 경우 데이터가 이진 트리의 높이만큼 이동을 할 수 있다.

따라서 데이터를 추가하는데 걸리는 시간은 O(log n) 이다.

Extract

이번엔 Heap 에서 데이터를 빼는 과정을 살펴보자.

 

1. Heap 의 루트 노드의 데이터를 pop 한다.

max-heap 기준으로는 배열에서 제일 큰 값이 빠져나온다.

 

그림과 같은 상황이 되며, 16이 빠져나간다.

 

2. 힙을 만들기 위해 배열의 맨 마지막 원소를 루트로 넣어준다.

굉장히 독특한 방식인데, 일단 배열의 맨 마지막 원소를 루트에 넣어주고, 배열의 크기를 하나 줄인다.

 

위 그림과 같은 상태가 된다.

 

3. 힙을 만족할 때까지 위치를 바꿔 넣은 노드와 자식노드를 배교한다.

이제 루트노드와 자식 노드를 비교하면서 Max-Heap 이 유지되도록 순서를 바꿔주면 된다.

왼쪽 자식과 오른쪽 자식 중 더 큰 값과 비교하여 교환하면 된다.

 

왼쪽 자식 노드 14와 오른쪽 자식 노드 10을 비교해보니 왼쪽 자식 노드인 14가 더크다.

이제 루트 노드인 7을 왼쪽 자식 노드인 14와 비교한다. 14가 더 크니 스왑을 진행한다.

 

그림과 같은 상태가 된다.

 

다음으로 왼쪽 자식인 8과 오른쪽 자식인 11을 비교해보자.

11이 더 크므로, 7과 11을 비교한다.

11이 더 크므로 스왑을 진행한다.

 

그림과 같은 상태가 된다.

 

마지막으로 7과 자식노드 1을 비교해본다.

1이 더 작으므로 스왑이 진행되지 않는다.

따라서 여기에서 멈추면 Max-Heap이 유지되었다.

---

다시 우선순위 큐로 돌아와서...

지금까지의 내용을 정리하면,

앞에서 우선순위 큐의 개념과 이를 구현하기 위한 방법으로 연결리스트를 사용하는 방법을 살펴보았다.

그런데 연결리스트를 사용하면 추가/삭제 중 하나에 대해 O(n) 시간이 걸려 비효율적이었다.

그래서 더 효율적인 자료구조로 구현하고자 새로운 자료구조인 Heap에 대해 정리하였다.

 

Heap 자료구조는 데이터의 추가와 삭제가 모두 O(log N) 시간에 수행된다.

따라서 Heap 자료구조를 사용해 우선순위 큐를 구현하면 연결리스트로 구현할 때보다 압도적으로 빠르게 구현할 수 있다.

 

그리고 이 Heap 을 사용하였을 때, 할 수 있는 작업이 더 있다.

바로 정렬이다.

어떤 데이터를 힙을 이용해 오름차순으로 정렬한다면, 그저 데이터를 힙에 쭉쭉 push 한 다음, min-heap 에서 데이터를 하나씩 빼기만 하면 된다.

만약 정렬하려는 데이터의 개수가 N개라면, push 를 N번, pop 을 N번 하므로, O(N log N) 시간에 정렬을 할 수 있다.

 

이렇게 Heap 을 이용한 정렬 방법을 가리켜, Heap Sort 라고 한다.

(하지만 실제 Heap-Sort 의 구현은 이것보다 더 효율적으로 수행되도록 구현되어 있다. 이미 주어진 데이터 배열에 대해 Build Heap 연산을 적용하여 선형시간에 힙을 만들 수 있다.)