[DataStructure] 2. 자료구조 기본 - Heap(Max heap, Min heap)에 대해서

Heap 자료구조

자료구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree 이다. 배열에 트리의 값들을 넣어줄 때, 0번째는 건너뛰고 1부터 루트노드가 시작된다. 이는 노드의 고유번호 값과 배열의 index를 일치시켜 혼동을 줄이기 위함이다. 힙에는 최소힙(min heap), 최대힙(max heap) 두 종류가 있다. Max Heap이란, 각 노드의 값이 children 의 값보다 크거나 같은 complete binary tree를 말한다. ( min heap은 그 반대이다. )

Max heap에서는 Root node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complextiry이 O(1)이다. 그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. (즉, random access가 가능하다. Min heap 에서는 최소값을 찾는데 소요되는 연산의 time complexity가 O(1)이다. )

배열에 저장하였을 때의 장점을 살리기 위해서는 인덱스 값을 알아야 한다.

어떻게 알아낼 수 있을까. 

complete binary tree는 노드의 개수가 n개 일 때, i번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.

Heapify

두 개의 subtree가 max-heap 일 때 root를 포함한 전체가 heap이 되도록 위치를 조정하는 과정을 말한다. 루트에서 작은 값이 흘러내려가면서 처리되는 방식(float-down)으로 진행된다. Max heapify의 경우, root가 child보다 작으면 두 개의 child 중 값이 큰 노드와 root를 교체하고, 교체할 노드가 없을 때까지 (처음에 root였던 노드가 leaf node로 될 때까지) 반복해준다.

최대값 추출

최대값을 추출하는 기능이 필요하다. 또는 최소값을 추출하는 자료구조를 결정하려고 한다.

그럴 때, heap 자료구조를 사용한다. 어떻게 하는가?

Max Heap에서 최대값은 루트 노드이다. 최대값을 추출하는데는 <Big-O(1)>의 시간이 소요된다. 하지만 이게 다가 아니라 루트 노드가 사라진 다음에도 트리는 Max Heap을 만족해야 한다. 즉, heapify를 해줘야 하는 것이다. 배열을 기반하였기 때문에 인덱스로 접근하여 heap 에서 가장 마지막 원소를 root에 옮기고 heapify 를 해준다. 이 마지막 원소를 root에 추가하여 heapify 하는 과정은 <big-O(log n)>이 된다.

새로운 값 삽입

heap에 새로운 값이 삽입되는 경우에는 어떤 조치를 취해줘야 heap의 형태가 유지될 수 있을까?

 ( Max heap의 경우 )  일단 새로 들어온 노드의 값이 제일 작다고 가정하자. 그리고 그 값을 배열의 제일 마지막에 삽입을 한 뒤, 부모 노드와 비교하면서, 역 heapify를 해준다. 삽입된 노드의 값이 부모 노드와 비교했을 때, 그 값이 더 크다면, 부모 노드와 swap이 일어날 것이고, 더 작다면, 그 상태로 max heap 자료구조의 성질을 만족하므로 비교를 멈춘다. 이렇게 삽입이 이루어진다.

이를 이용한 heap sort 구현은 다른 sorting 의 알고리즘과 함께 소개한다.

end