[자료구조] 이진 힙, 바이너리 힙 (Binary Heap) 이란?

[자료구조] 이진 힙, 바이너리 힙 (Binary Heap) 이란?

알아두면 좋을 것들

- key, value 쌍을 딕셔너리 value, 혹은 딕셔너리 페어라고도 한다.

- 아래의 글에선, 노드와 엔트리를 같은 의미로 썼다.

- 아래의 글은, Min heap을 기반으로 썼다. (Max heap이라고 큰 차이가 있는 건 아니다. 단지 heap-order property가 다를 뿐)

의미/특징

바이너리 힙의 예시, 빨간 숫자 2가 루트 노드이며, 제일 작다. 또한, 부모노드는 항상 자식노드보다 작은, heap-order property를 가지고 있다.

- 바이너리 힙은 힙(Heap)의 종류 중 하나.

- 바이너리 힙은 자식이 무조건 2개를 가져야한다.

- 바이너리 힙은 Complete binary tree(완전 이진트리) 속성을 가지고 있다.

- Complete binary tree는 가장 밑의 레벨을 제외하고, preferct binary tree이어야 하고, 가장 밑의 레벨의 노드들은 왼쪽부터 채워져있어야 한다. 그것이 Complete binary tree이다. 그 외는 Complete binary tree가 아니다.

- 중요한 성질은, 모든 엔트리(혹은 노드)가 heap-order property (힙-순서 속성)을 만족해야한다.

- heap-order property는 부모의 key가 자식의 key보다 항상 작아야, 혹은 커야하는 속성을 말한다.

바이너리 힙의 설계

여러가지 방법이 있지만, 예시로, 배열(arrays)를 통해서 설계하는 방법을 알아보겠다.

배열로 설계 할 때, Level-order traversal (트리의 레벨 순서대로 조회)를 이용하여 배열에 저장한다.

아래의 그림에 보듯이, 배열에 저장되는 순서 1, 2, 3, 4, .. 가 a, b, c, d, ... 순서로 저장되는 것을 볼 수 있다. 이것이 Level-order traversal 순서이다. 즉, 이 순서로 배열에 저장된다.

배열(arrays)를 통해서, Level-oder traveral 순서로 설계할 때, 아래의 규칙이 지켜져야한다.

규칙 1. 배열의 0번째는 사용하지 않는다.

규칙 2. i 노드의 자식은 배열의 2i번째, 2i+1번째의 값이 해당된다. ( node[i]의 자식은, node[2i] 그리고 node[2i+1]

규칙 3. 그 말은, noed[i]의 부모는 node[i/2] (소숫점이하 버림)이 되는 것이다.

동작 (Operations)

아래와 같은 동작들이 있다. 요약하면, min, insert, 그리고 removeMin() 이다.

Entry min()

1. 노드 중에서 Root노드를 반환한다

Entry insert(key, value)

1. 노드(k, v)를 가진 x가 있다.

2. 이 x는 트리의 가장 낮은 레벨에서, 현재 빈 공간(왼쪽에서부터 차례대로 채워지는)에 위치한다. (배열 인덱스로는 가장 마지막 인덱스가 해당된다)

3. heap-order property를 검사하고, 만족할 때까지 계속 고친다. (자식노드는 부모보드보다 항상 커야한다)

(즉, x의 key와 부모의 key를 비교하여, 그것이 작으면 교환한다. 이것을 property가 만족할 때 까지 반복한다.)

단계1(왼쪽)을 먼저 수행 후, 그래도 property가 만족하지 않아서, 단계2(오른쪽)을 수행한다.

Enter removeMin() (혹은 removeMax)

1. 루트 노드를 제거한다.

2. 그 값을 반환한다.

3. 트리의 가장 마지막의 노드를 가져와, 루트노드에 채운다.

4. heap-order property를 검사하고, 만족할 때까지 계속 고친다.

(즉, x가 자식들 중 하나, 혹은 두개의 자식보다 크면, x와 자식들이 가진 값 중 최소 값을 가진 자식과 교환한다. 이것을 property가 만족할때 까지 반복한다.)

순서1(왼쪽)에서는, root노드를 제거 후, 가장 마지막 노드와 교체한다. 순서2(오른쪽)에서는, 자식이 2개가 있음을 나타낸다.

순서3(왼쪽)에서는, 가장 자식을 선택하고, 순서4.(오른쪽)에서는 heap-order property를 맞추기 위해, exchange한다.

복잡도

Complexity

Searh Insert Remove Max/Min Array (unsorted) O(n) O(1) O(n) O(n) Array (sorted) O(log2n) O(n) O(n) O(1) Linked List O(n) O(1) O(n) O(n) Binary Heap O(log2n) O(log2n) O(log2n) O(1)

코드구현

인용/참고자료

한양대학교 - 데이터 구조론 (우선순위 큐)

http://www.kocw.net/home/cview.do?cid=ec066a0f24e13e9a

from http://i5i5.tistory.com/559 by ccl(A) rewrite - 2021-10-17 02:00:50