우선순위 큐의 이해
우선순위 큐는 이름에서 알 수 있듯이 큐와 관련이 있는 자료구조이다.
당연하겠지만 큐와 큰 차이가 있다.
'큐'의 핵심은 다음과 같다.
선입선출(FIFO) 들어온 순서대로 나간다.
- enqueue: 큐에 데이터를 삽입한다.
- dequeue: 큐에 데이터를 꺼낸다.
우선순위 큐의 핵심은 다음과 같다.
들어온 순서에 상관없이 우선순위가 높은 데이터가 먼저 나간다.
- enqueue: 우선순위 큐에 데이터를 삽입한다.
- dequeue: 우선순위가 높은 데이터를 꺼낸다.
우선순위 큐의 우선순위는 프로그래머가 결정할 일이다.
숫자가 큰 것이 우선순위가 높을 수도 있고 작은 것이 높을 수도 있고 특정한 조건에 의해서 우선순위가 결정될 수도 있는 일이다.
참고로 우선순위가 같은 데이터도 존재할 수 있다.
우선순위 큐의 구현 방법
우선 순위 큐를 구현하는 방법은 다음 세 가지로 구분할 수 있다.
1. 배열 기반 구현
2. 연결 리스트 기반 구현
3. 힙을 이용한 구현
배열이나 연결 리스트를 이용하면 우선순위 큐를 아주 간단하게 구현할 수 있다.
배열로 구현하는 경우
우선순위 큐를 배열로 구현하는 경우는 두 가지 단점이 존재한다.
데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반한다.
이는 배열의 대표적인 단점이라 할 수 있다.
하지만 더 큰 문제는 다음과 같다.
삽입 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.
이는 우선순위가 가장 낮은 데이터를 저장하는 경우 최악이다.
연결 리스트로 구현하는 경우
연결리스트로 구현하는 경우는 배열의 첫 번째 단점은 없지만, 두 번째 단점이 남아있다...
결론
우선순위 큐는 배열도 연결 리스트도 아닌 '힙'이라는 자료구조를 이용해 구현하는 것이 일반적이다.
힙(Heap)의 소개
힙은 '이진 트리'이되 '완전 이진 트리'이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값이 가장 커야한다.
힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이므로
이를 활용하면 쉽게 우선순위 큐를 구현할 수 있을 것이다.
참고로 힙은 무엇인가를 쌓아 놓은 더미와 흡사하여 지어진 이름이다.
영단어 heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 지닌다.
힙의 구현과 우선순위 큐의 완성
힙의 구현은 곧 우선순위 큐의 완성으로 이어진다. 하지만 둘은 같은 개념은 아니다.
힙은 우선순위 큐의 구현에 딱 어울리는, 완전 이진 트리의 일종이다.
힙에서의 데이터 저장 과정
새로운 데이터는 우선순위가 제일 낮다는 가정하에서 '마지막 위치'에 저장한다. 그리고 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔준다. 바뀐 다음에도 계속해서 부모 노드와 비교한다. 제대로 된 위치를 찾을 때까지.
힙에서의 데이터 삭제 과정
힙에서 데이터의 삭제는 우선순위가 가장 높은 요소를 꺼내는 행위이다.
즉 루트 노드를 삭제하는 것이다.
루트 노드를 삭제하는 것은 어렵지 않다. 문제는 삭제 후에도 힙의 구조를 유지해야 한다는데 있다.
마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다.
힙의 구현은 연결리스트? 배열?
힙을 구현하는데는 일반적으로 배열을 사용한다. 왜냐하면 연결리스트를 기반으로 힙을 구현하면 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않기 때문이다. 하지만 배열은 간단히 추가할 수 있기 때문에 힙은 배열로 주로 구현한다.
배열을 기반으로 힙을 구현하는데 알아야 할 것
노드에 고유의 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다.
참고로 구현의 편의를 위해서 인덱스 0의 위치는 사용하지 않는다.
왼쪽과 오른쪽 자식과 부모 노드의 인덱스 값을 얻는 방법을 알아보자.
- 왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 * 2
- 오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값* 2 + 1
- 부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2 (정수형 나눗셈)
이후 힙 자료구조를 구현해 보았다.
