Published 2021. 12. 2. 02:02

[자료구조] 우선순위 큐와 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)에서 최댓값을 삭제하는 방법