자료구조 - Heap

자료구조 - Heap

* Heap이란?

1. Complete binary tree이면서

   : 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외하고는 다채워진, 자식이 추가될 때 왼쪽부터 추가되는 트리

2. Heap Property를 만족하는 것

    1) max heap property : 부모는 자식보다 크거나 같다.

    2) min heap property : 부모는 자식보다 작거나 같다.

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

• A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

트리의 height = log N

출처 : https://ko.wikipedia.org/wiki/힙_(자료_구조)

* 정렬할 배열을 heap으로 만들기

Heap은 1차원 배열로 표현이 가능하다.

트리의 레벨 1부터 마지막 레벨까지 sibling들을 순서대로 넣어주면 된다.

위 예제를 배열로 표현해보면

A = {-, 100, 19, 36, 17, 3, 25, 1, 2, 7}

루트 노드 : A[1]

A[i]의 부모 : A[i/2]

A[i]의 왼쪽 자식 : A[2*i]

A[i]의 오른쪽 자식 : A[2*i + 1]

배열의 끝에서부터 역순으로 출발하여(<- 방향), 처음으로 leaf노드가 아닌 노드에서 시작한다.(맨 마지막 노드의 부모 노드 = A[N/2])

// 배열을 힙으로 만든다

// 시간복잡도 : O(N)

BUILD-MAX-HEAP(A)

{

heap-size[A] <- length[A]

for i <- length[A]/2 downto 1

do MAX-HEAPIFY(A, i)

}

* 기본 연산 (Heapify)

complete binary tree에서 루트 노드만 heap property를 만족하지 않을 때, 전체 트리를 heap property를 만족하도록 하게 하는 연산

(즉, 왼쪽 서브 트리도 heap이고 오른쪽 서브 트리도 heap이지만, 루트 노드만 heap property를 만족하지 않을 때)

// 노드 i를 루트로 하는 서브 트리를 heapify한다.

MAX_HEAPIFY(A, i)

{

if there is no child of A[i]

return;

k <- index of the biggest child of i;

if A[i] >= A[k]

return;

exchange A[i] and A[k]

MAX_HEAPIFY(A, k)

}

* Heap Sort

1. 주어진 배열을 heap으로 만든다.

2. heap에서 루트값을 마지막 값과 바꾼다.

3. 힙의 크기가 1 줄어든 것으로 간주. 마지막 값을 무시하면 된다.

4. 루트 노드에 대해 Heapify

5. 2~4 번 반복

HEAP-SORT

{

BUILD-MAX-HEAP(A) // O(n)

for i <- heap_size downto 2 do // N-1 times

exchange A[1] and A[i] // O(1)

heap_size <- heap_size - 1 // O(1)

MAX-HEAPIPY(A, 1) // O(logN)

}

-> 시간복잡도 : O(N logN)