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

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

우선순위 큐와 Heap

우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 데이터가 먼저 나갈 수 있도록 만들어진 자료구조입니다.

스택과 큐, 우선순위 큐에서 먼저 삭제되는 데이터

그래서 어떻게 구현하는데?

우선순위 큐는 배열 또는 연결리스트을 단순하게 사용하여도 구현이 가능합니다. 배열과 연결리스트의 맨 앞 원소부터 차례대로 우선순위가 높은 data를 넣는다면 어렵지않게 우선순위 큐를 구현할 수 있습니다. 이러한 방식으로 우선순위 큐를 구현하게 되면 우선순위에 맞춰 data를 알맞은 자리에 삽입해야 하기 때문에 이 과정이 O(n)의 시간복잡도가 소요됩니다. 하지만 heap 자료구조를 사용한다면 조금 더 효율적인 방식으로 우선순위 큐를 구현할 수 있습니다.

heap을 사용한다면?

우선 heap이 무엇인지에 대해 알아보겠습니다.

heap 이란? 힙(heap)은 완전이진트리를 기본으로 한 자료구조입니다.

완전 이진트리란 아래 사진과 같이 포화 이진트리 (leaf 노드를 제외한 internal 노드들이 전부 차있는 이진 트리) 에서 오른쪽 리프부터 제거하여 얻은 트리입니다. 포화 이진트리 (Full Binary Tree)와 완전 이진트리 (Complete Binary Tree)의 예시

힙에서의 노드간의 관계는 아래와 같습니다. A가 B의 부모노드이면, A의 key 값은 B의 key값과 대소관계가 성립 합니다. 이 대소관계에 따라 최소 힙 또는 최대 힙으로 나뉘는데 최소 힙의 경우 부모 노드의 key 값이 항상 자식 노드보다 작고, 최대 힙은 반대입니다. 이 때 부모 자식간의 대소관계는 성립되지만 형제 노드간에는 대소관계가 성립하지 않습니다. 최대 힙과 최소 힙의 예시

heap의 구현 힙을 저장하는 표준적인 자료구조는 배열 입니다.

구현 편의를 위해 배열의 첫 번째 인덱스인 0은 사용하지 않는다고 가정합니다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않습니다. 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3입니다.

힙에서의 부모 노드와 자식 노드의 관계 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1 부모의 인덱스 = (자식의 인덱스) / 2

배열에서 힙 형태로 자료를 저장하는 방식

heap에서의 삽입 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입 합니다.

새로운 노드를 부모 노드들과 교환 해서 힙의 성질을 만족시킵니다. 예시) 아래 그림과 같은 최대 힙(max heap)에 새로운 요소 8을 삽입하는 방법

heap에서의 삭제 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됩니다. 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것입니다.

삭제된 루트 노드에는 힙의 마지막 노드를 가져옵니다.

힙을 재구성합니다. 예시 ) 아래 그림과 같은 최대 힙(max heap)에서 최댓값을 삭제하는 방법

그래서 Heap을 이용한다면...

위의 내용을 정리하면 heap을 사용했을 때 data의 삽입과 삭제가 시간 복잡도가 O(logN) 가 된다는 사실을 알 수 있습니다.

또한 heap의 root 노드의 값은 항상 우선순위가 제일 높은값(혹은 제일 낮은 값)이므로 우선순위 큐를 구현하기에 적절하다는 것을 알 수 있습니다.

따라서 배열이나 링크드 리스트를 단순하게 사용한 것보다 삽입에서의 시간복잡도가 많이 줄어들고 이에 좀 더 효율적으로 우선순위 큐를 구현해 볼 수 있습니다.

References

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

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

from http://kjhoon0330.tistory.com/6 by ccl(A) rewrite - 2021-12-02 03:01:21