자료구조(9) 우선순위 큐와 힙

우선순위 큐는 그 이름이 의미하듯 큐와 관련이 있다. 하지만 공부하다보면 그 관계가 깊지 않다고 느낄지도 모르겠다. 제목만 봐서는 앞서 구현한 "큐"를 확장하는 수준에서 마무리가 될 것 같지만 "큐"의 구현과 "우선순위 큐"의 구현에는 많은 차이가 있다.

 

큐의 핵심 연산 두가지

• enqueue : 큐에 데이터를 삽입하는 행위
• dequeue : 큐에서 데이터를 꺼내는 행위

 

우선순위 큐의 핵심 연산 두가지

• enqueue : 우선순위 큐에 데이터를 삽입하는 행위
• dequeue : 우선순위 큐에서 데이터를 꺼내는 행위

 

반면 연산의 결과에는 차이가 있다. 큐의 연산 결과로, 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산결과는 다음과 같다.

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

때문에 큐를 가리켜 "줄서기"에 비유한다면, 우선순위 큐는 "응급상황"에 비유할 수 있다.

 

질문 List

• 우선순위 큐에 저장되는 데이터들은 모두 우선순위를 지녀야 하나요? 우선선위는 어떻게 결정하나요?

답변 : 우선순위를 지녀야 한다기보다, 데이터를 근거로 우선순위를 판단할 수 있어야 한다.

• 결국 우선순위의 비교를 위해서는 우선순위 정보가 정수로 표현되어야 하겠네요?

답변 :  틀린 말은 아니다. 예를들어 영단어 사전편찬순서의 경우다. 하지만 이 역시 아스키코드(정수)의 비교가 진행되기때문에 결과적으로 정수의 비교이다.

• 그럼 정수의 값이 클 수록 우선순위가 높은 건가요? 아니면 낮을 수록 높은 건가요?

답변 :  결정하기 나름이다.

• 우선순위가 같은 데이터가 존재할 수 있나요?
• 답변  : 당연하다. 그렇지 않으면 자료구조로써 활용할 수 있는 범위가 매우 제한적이지않은가?

 

우선순위 큐를 구현하는 3가지 방법

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

 

배열의 단점

1. 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다.
2. 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

연결 리스트의 단점

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

데이터의 수가 적은 경우 큰 단점이 되지 않을 수 있다. 하지만 데이터의 수가 많아지면, 그래서 연결된 노드의 수가 많아지면, 노드의 수에 비례해서 성능을 저하시키는 주원인이 된다. 그래서 우선순위큐는 단순 배열도 연결 리스트도 아닌 "힙"이라는 자료구조를 이용해서 구현하는 것이 일반적이다.

 

힙의 간단한 정의

"힙은 '이진 트리'이되 '완전 이진 트리'이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노트에 저장된 값이 가장 커야 한다."

 

최대 힙 : 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리

최소 힙 : 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리

 

힙의 구현은 곧 우선순위 큐의 완성으로 이어진다. 따라서 힙과 우선순위 큐를 동일하게 인식하는 경향이 매우 강하다. 하지만 이는 정확하지 않은 것이니, 우선순위 큐와 힙을 어느정도 구분할 수 있으면 좋겠다. 힙은 우선순위 큐의 구현에 딱 어울리는, 완전 이진 트리의 일종이라는 사실을 기억하기 바란다.

 

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

 

힙에서의 데이터 저장과정 (2가지 일련과정)

"새로운 데이터는 우선순위가 제일 낮다는 가정하에서 "마지막 위치(노드를 추가한 이후에도 완전 이진 트리가 유지되는 마지막 레벨의 가장 오른쪽)"에 저장합니다. 그리고는 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔줍니다. 바뀐 다음에도 계속해서 부모 노드와 비교합니다. 제대로 된 위치를 찾을 때까지 말이지요"

 

힙에서의 데이터 삭제과정 (2가지 일련과정)

우선순위 큐의 삭제는 "가장 높은 우선순위의 데이터 삭제"를 의미한다 그러면 힙에서 루트 노드를 삭제한 다음에 이 부분을 어떻게 채울 것 인가? = "마지막 노드를(이진 트리에서 마지막 레벨의 가장 오른쪽) 루트 노드의 자리로 옮긴 다음에, 자식 노드와 비교를 통해서 제자리를 찾아가게 한다" 참고로 우선순위가 낮은 자식 노드와 교환하면 안되는 이유는, 그렇게 했을 경우 힙의 기본 조건이 무너지기 때문이다.(당연한얘기)

 

삽입과 삭제의 과정에서 보인 성능의 평가

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

우선순위가 낮은 데이터를 배열에 저장하는 경우, 배열에 저장된 모든 데이터와 우선순위 비교과정을 거쳐야 하므로 데이터의 저장의 시간복잡도는 O(n)이 되고, 삭제의 과정에서는 맨 앞에 저장된 데이터를 삭제하면 되기때문에, 이 경우 시 복잡도는O(1)이 된다.

 

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

우선순위가 높을수록, 데이터를 연결 리스트의 앞 부분에 배치하는 방식이므로 배열의 경우와 다를 바가 없다.

 

• 힙 기반 데이터 저장의 시간 복잡도 : O(log2n)
• 힙 기반 데이터 삭제의 시간 복잡도 : O(log2n)

힙은 완전 이진 트리이므로, 힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때 마다 두 배씩 증가한다. 때문에 데이터의 수가 두 배 늘 때마다, 비교연산의 횟수는 1회증가한다. 이로써 우선순위 큐의 구현에 있어서 배열보다도 연결 리스트보다도 힙이 어울리는 이유를 객관적으로 보여주었다.

 

우선순위 큐의 구현에 어울리는 것은 힙으로 결론이 났다. 이제는 힙의 구현방법에 대해서 고민해야 한다.

왜냐하면 힙은 트리이기 때문이다. 앞서 트리를 구현하는 방법에는 "배열"을 이용하는 방법과 "연결 리스트"를 이용하는 방법이 있었다. "힙은 배열을 기반으로 구현해야 한다" 실제로 힙의 구현은 배열을 기반으로 구현하는 것이 원칙으로 여겨지고 있는데, 그 이유는 다음과 같다.

"연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 "마지막 위치"에 추가하는 것이 쉽지 않다"

사소한 이유 같고, 그래서 연결리스트를 기반으로도 쉽게 해결 가능한 문제처럼 보이지만, 이는 결코 간단한 문제가 아니다. 하지만 배열 기반의 힙이라면 이는 매우 간단한 문제가 된다.

 

배열 기반으로 트리를 구성 하는 방법

"노드에 고유의 호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다. 참고로 첫번째 인덱스 [0]은 비워두는것이 편하다"

 

배열을 기반으로 힙을 구현하기 위해 알아야할 것들

"왼쪽 그리고 오른쪽 자식 노드의 인덱스 값을 얻는 방법, 그리고 부모 노드의 인데그 값을 얻는 방법"

자식 노드의 인덱스 값을 얻는 방법은 데이터의 삭제를 위해서, 부모 노드의 인덱스 값을 얻는 방법은 데이터의 추가를 위해서 필요하다

 

• 왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2
• 오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2 + 1
• 부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2

의외로 간단하다. 이진 트리는 레벨이 증가함에 따라서 추가할 수 있는 자식 노드의 수가 두 배씩 증가하는 구조다 보니, 2를 나누고 곱하는 방식으로 부모 노드와 자식의 인덱스 값을 구할 수 있다. 한가지 주의할 점은 부모 노드의 인덱스 값을 구하기 위한 나눗셈 연산은 정수형 나눗셈라는 점이다. 즉 5를 2로 나누었을 때의 결과는 2.5가 아니라 2가 되어야 한다.

 

원리 이해 중심의 힙 구현 : Hdelete 함수에 대한 설명 중심

(완전한 코드가 아닌 이해를 돕기위한 코드)

• 힙은 완전 이진 트리이다
• 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다

• 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다
• 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다
• 우선순위를 나타내는 정수 값이 작을 수록 높은 우선순위를 나타낸다고 가정한다

1. 함수 GetHiPiriChildIDX에 노드의 인덱스 값을 전달하면, 이 노드의 두 자식 노드중에 우선순위가 높은 것의 인덱스 값을 반환한다
2. 함수 GetHiPiriChildIDX는 자로 전달된 노드에 자식 노드가 없으면 0을 반환하고, 자식 노드가 하나인 경우에는 그 노드의 인덱스 값을 반환한다

앞서배운 삭제과정

"힙의 마지막 노드를 루트 노드의 위치에 올린 다음에, 자식 노드와의 비교과정을 거치면서 아래로 내린다.

자신의 위치를 찾을 때 까지 내린다." 하지만 우리는 다음과 같이 판단 할 수 있다

"루트 노드로 올려진 마지막 노드는 자신의 위치를 찾을 때까지 아래로 이동하면서 자신의 위치를 찾아간다. 하지만 이런 번번한 이동은 코드에 그대로 담을 필요는 없다. 최종 목적지가 결정되면 단번에 그리로 옮기면 된다"

 

"함수 HDelete에서는 마지막 노드가 있어야 할 위치를 parentIdx에 저장된 인덱스 값을 갱신해가며 찾아가고 있다"

 

올릴땐 올리고, 내릴 땐 실제로 내리지 않으면서 위치정보만 갱신한다.(연산의 최소화)(코드봐야 이해됨)

 

원리 이해 중심의 힙 구현 : Hinsert 함수에 대한 설명 중심으로

"새로운 데이터는 우선순위가 제일 낮다는 가정하에 '마지막 위치'에 저장합니다. 그리고는 우선순위의 비교를 통해서 자신의 위치를 찾을 때 까지 위로 올립니다" Hdelete 함수를 구현할 때와 마찬가지로 Hinsert 함수를 구현 할때에도, 새로운 데이터가 담긴 노드를 이리저리 이동시킬 필요가 없다. 새로운 노드가 있어야 할 위치의 인덱스 값만 유지를 해도 된다.

 

내릴땐 실제로 내리고, 올릴땐 실제로 올리지 않으면서 위치정보만 갱신한다.(연산의 최소화)(코드봐야 이해)

 

제법 쓸만한 수준의 힙 구현 : 힙의 변경(실제 힙구현을 위해 원리 이해 중심의 힙 구현에서 수정해야할 코드)

 

• 구조체는 힙을 이루는 노드를 표현한 것인데, 이 구조체 멤버로 우선순위 정보를 담는 변수가 선언된것
• Hinsert 함수에서 우선순위를 결정하고 그 값을 전달하라고하는것

"우선순위 라는 것이 데이터를 기준으로 결정되는 경우가 대부분인데, 우선순위 결정 기준을 알려달라는 것도 아니고, 우선순위를 직접 결정해서 알려달라는건 매우 불편하다" 따라서 프로그래머 우선순위 판단 기준을 힙에서 설정할 수 있어야 한다. 프로그래머가 우선순위의 판단 기준을 힙에서 설정할 수 있다는 것은, 힙의 적용 범위와 활용 방법이 넓어짐을 의미한다.