[자료구조] 힙과 우선순위 큐

1. 힙

 힙은 트리 글에서 정리한 완전 이진 트리에 속하는 자료구조이다. 그래서 완전 이진 트리의 특성을 모두 지니고 있다.

(완전이진트리의 특성: 모든 노드는 왼쪽 노드부터 채워져야하고, 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있다.)

 

힙은 최대힙과, 최소힙이 존재한다.

 

최대힙(Max Heap)

- 부모 노드의 값은 항상 자식보다 크거나 같다. (좌우 순서는 상관없다)

- 루트 노드는 언제나 트리의 최댓값이다.

- 값의 중복을 허용.

 

최소힙(Min Heap)

- 부모노드의 값은 항상 자식보다 작거나 같다. (좌우 순서는 상관없다.)

- 루트 노드는 언제나 트리의 최솟값이다.

- 값이 중복을 허용.

 

이러한 힙은 일차원 배열로 구현이 가능하다.

인덱스 1부터 루트노드부터 값을 넣어주면 아래와 같은 방법으로 인덱스를 통해 노드 접근이 가능하다.

 

루트 노드: 인덱스 1

부모 노드 찾기: 자식 인덱스 / 2

왼쪽 자식 노드 찾기: 부모 인덱스 * 2

오른쪽 자식 노드 찾기: 부모 인덱스 *2 + 1

 

2. 우선순위큐

 우선순위 큐는 데이터들이 우선순위에 따라 처리되는 자료구조로서, 일반적인 큐와 달리 데이터가 큐에 추가되거나 제거될 때 우선순위에 의해서 독작하는 자료구조 입니다.

 우선순위 큐는 힙을 기반으로 구현 됩니다.

3. 시간복잡도

 힙은 데이터의 최댓값 또는 최솟값을 순차적으로 가져오기 위해서 만들어 졌기 때문에 최댓/최솟값을 찾는 연산과 삽입/삭제가 대표적인 연산이라고 볼 수 있다.

 1) 최댓값 또는 최솟값 찾기 : O(1)

  최대 힙일 경우에는 최댓값, 최소 힙일 경우에는 최솟값이 항상 루트노드이기 때문에 루트노드의 값을 가져오게 되면 최댓값과 최솟값에 바로 접근이 가능하다.

 2) 삽입

 최대 힙은 삽입 후에 Heapify 연산을 통해 힙을 재 구조화 하는데, 이 힙 구조는 이진트리이므로 최대 O(logN)의 시간 복잡도가 발생한다. (넣은 값이 최대 또는 최솟값일 경우 logn번 걸림)

 2) 삭제

 삭제 또한 루트노드가 삭제된 뒤 맨 마지막 노드를 루트에 넣고, Heapify 연산을 하기 때문에 최대 O(logn)의 시간 복잡도가 발생한다.

(삭제 후 맨 마지막 노드가 리프노드 전 단계의 모든 노드 값보다 작거나(Max Heap일 경우) 클 때(Min Heap일 경우) logn)

 

4. Heap의 재 구조화 Heapify

 삽입 또는 삭제 연산이 발생했을 경우 Heap을 재구조화 하는 Heapify 연산이 발생하게 되는데 그 원리에 대해서 살펴보자.

최대힙의 삽입 Hepify 연산

 

최대힙의 삭제 Heapify 연산

 

최소힙은 최대, 최소만 다를 뿐 연산 메커니즘은 동일하기 때문에 최대 힙만 그림으로 그려보았다.

5. 정리

 1. 힙은 완전이진탐색 트리의 일종이다. 그렇기 때문에 완전 이진 탐색 트리의 특성을 가지고 있다.

 2. 힙은 최대 힙, 최소 힙이 존재한다. 이들의 루트노드는 각각 최댓값, 최솟값이다.

 3. 최대, 최소 접근에는 O(1)의 시간 복잡도, 삽입, 삭제에는 O(logn)의 시간복잡도가 발생한다.

 4. 힙은 삽입, 삭제 연산시 Heapify라는 트리를 재구조화 하는 작업이 발생한다.