[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐(Priority Queue)

일반적인 큐(Queue)는 FIFO(First-In First-Out) 구조로 먼저 들어간 데이터가 먼저 나오는 구조이지만

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조이다.

 

우선순위 큐의 예시

자료구조를 사용해 "병원의 응급실 환자를 처리하는 시스템"을 만든다고 가정해보자.

 

📌스택(Stack)

스택은 LIFO(Last-In First-Out) 구조로 마지막에 들어온 사람이 먼저 나가게 됩니다.

그럼 가장 먼저 응급실에 실려온 사람이 가장 나중에 진료를 받게 되겠죠? 뭔가 이상합니다.

 

📌큐(Queue)

큐는 FIFO(First-In First-Out) 구조로 먼저 들어온 사람이 먼저 나가게 됩니다.

그럼 가장 먼저 응급실에 실려온 사람이 가장 먼저 진료를 받게 되겠죠? 공평하긴 합니다.

 

📌우선순위 큐(Priority Queue)

마지막으로 우선순위 큐는 급한 사람이(우선순위가 높은) 먼저 나가게 된다.

그럼 먼저 왔더라도 더 급한 환자가 있으면 급한 환자가 먼저 진료를 받게 된다. 이게 가장 어울릴 것 같네요.

 

만약, 우선순위 큐가 아닌 일반적인 큐의 방식을 사용한다면 정말 위급한 환자가 응급실로 실려왔을 때 앞서 도착한 환자들이 모두 진료가 끝날 때까지 이 환자는 기다려야 한다. 하지만 우선순위 큐를 사용한다면 상황에 맞게 급한 환자가 먼저 진료를 받을 수 있다.

 

우선순위 큐 실습

우선순위 큐를 구현하는 방법은 배열, 연결 리스트, 힙 세 가지가 있다.

- 우선순위 큐(Priority Queue) 실습(feat. 배열)

- 우선순위 큐(Priority Queue) 실습(feat. 연결 리스트)

- 우선순위 큐(Priority Queue) 실습(feat. 힙)

 

우선순위 큐와 힙을 같이 포스팅 한 이유는 우선순위 큐는 힙이라는 자료구조를 가지고 구현할 수 있기 때문이다.

우선순위 큐에 배열과 연결 리스트를 사용하면 여러가지 단점이 많아 일반적으로 '힙'이라는 자료구조를 사용한다.

그래서 힙이라는 자료구조를 이용한 우선순위 큐 구현만 포스팅 할 예정이다!

 

힙(Heap)

- 힙(Heap)은 완전 이진 트리의 일종이다. (완전 이진 트리란?)

- 여러 개의 값들 중에서 최댓값, 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

- 부모 노드에 저장된 값(우선순위)은 자식 노드에 저장된 값(우선순위)보다 크거나 같아야 한다.

(최대 힙에서는 높은 값이 우선순위가 되고, 최소 힙에서는 작은 값이 우선순위가 된다.)

 

📌최대 힙(max heap)

최대 힙(max heap)

- 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 '최대 힙'이라고 한다.

- 부모 노드의 키 값이 자식 노드의 키 값보다 커야 한다.

 

📌최소 힙(min heap)

최소 힙(min heap)

- 반면 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 '최소 힙'이라고 한다.

- 부모 노드의 키 값이 자식 노드의 키 값보다 작아야 한다.

 

⭐우선순위 큐와 힙?

힙은 우선순위 큐의 구현에 딱 어울리는 자료구조일 뿐 같은 개념은 아니다!

 

힙에서의 데이터 저장과정

힙을 구현하고 이를 기반으로 우선순위 큐를 구현할 것이다.

힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 먼저 알아야 한다.

 

데이터 추가 직전의 힙(최대 힙)

그림에 나와있는 최대 힙에서 26을 저장한다고 가정해보자. 데이터를 저장한 이후에도 *최대 힙의 조건을 만족시켜야 한다.

*최대 힙 조건 : 부모 노드의 데이터가 자식 노드의 데이터보다 커야 한다.

 

💡 데이터 삽입에서 아래 방법을 사용해서 힙의 조건을 만족시킬 수 있다.

1. 새로운 데이터는 힙의 마지막 노드에 이어서 삽입한다.

2. 새로운 노드와 부모 노드를 비교한 후 힙의 성질을 만족시킬 때까지 바꿔준다.

 

위 그림과 같이 마지막 노드에 26이라는 데이터를 추가하고 부모 노드와 비교를 한다. 최대 힙의 조건을 만족시키려면 부모 노드가 자식 노드보다 커야 하기 때문에 새로 추가된 노드와 기존 부모 노드의 위치를 바꿔주어야 한다.

 

노드를 변경한 후 이어서 부모 노드와 또 다시 비교를 한다. 이번에도 새로 추가된 노드가 부모 노드보다 더 크기 때문에 위치를 바꾸어준다.

 

마지막으로 루트 노드와 비교를 한다. 이번에는 새로 추가된 노드가 부모 노드보다 크지 않으니 숫자 26은 자신의 위치를 찾게 된 것이다. 이 그림이 26이라는 데이터를 추가한 최종결과인데 여전히 최대 힙의 조건을 만족하고 있다.

 

힙에서의 데이터 삭제과정

힙의 삭제과정은 가장 높은 우선순위의 데이터를 삭제해야 한다.

힙에서 가장 높은 우선순위는 루트가 될것이기에 가장 먼저 루트를 삭제하고 그 자리를 채워야한다.

 

💡 데이터 삭제에서 아래 방법을 사용해서 힙의 조건을 만족시킬 수 있다.

1. 루트 노드를 삭제한 후 트리의 가장 마지막 노드를 루트 자리로 삽입한다.

2. 바꾼 노드와 자식 노드를 비교한 후 힙의 성질을 만족시킬 때까지 바꿔준다.

 

가장 높은 우선순위인 루트를 삭제하고 삭제된 자리에 *마지막 노드를 삽입한다.

*마지막 노드 : 완전 이진 트리에서 마지막 레벨의 가장 오른쪽에 위치한 노드

 

삽입의 과정과 동일하게 비교를 하여 최대 힙의 조건을 만족시킨다.

값을 비교할 때 우선순위가 높은 자식 노드와 비교를 해야한다. 최대 힙에서 26보다 27의 우선순위가 더 높기 때문에 27과 비교를 진행한다. 그 결과 20은 27보다 우선순위가 낮기 때문에 교환한다.

 

다음도 마찬가지로 우선순위가 높은 자식 노드와 비교를 한 후 힙의 조건에 맞게 교환을 한다.

위 그림에서는 14와 17중 우선순위가 더 높은 17과 비교를 했고 그 결과 20이 우선순위가 더 높기 때문에 이 상태에서 삭제과정이 마무리 된다.

 

힙 실습

그렇다면 힙의 구현에 어울리는 것은 무엇일까?

- 힙(Heap) 실습(feat. 배열)

- 힙(Heap) 실습(feat. 연결 리스트)

 

완전 이진 트리의 구조를 갖고 또 그 구조를 유지해야 하는 '힙'은 배열을 기반으로 구현해야 한다. 실제로 힙의 구현은 배열을 기반으로 구현하는 것이 원칙으로 여겨지고 있다. 그 이유는 "연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않다."

 

 

References

📚 윤성우의 열혈 자료구조 : C언어를 이용한 자료구조 학습서

https://jina-developer.tistory.com/98

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=tylee80&logNo=30164453923