알고리즘 기초 04) 힙 (Heap) 자료 구조

사전 개념 : 우선순위 큐 (Priority Queue) 자료 구조

우선 순위의 개념을 queue에 도입한 자료 구조이다.

데이터들이 우선 순위를 갖고 있으며, 우선 순위가 높은 데이터가 먼저 빠져나간다.

 

대표적인 사용처 : 시뮬레이션 시스템, 네트워크 트래픽 제어, CPU scheduling, 수치 해석적인 계산 등

 

구현 : list (array), linked list, heap 등으로 구현이 가능하며, 이 중 heap으로 구현하는 것이 가장 효율적이다.

 

개념

complete binary tree의 일종으로 우선순위 큐의 구현을 위해서 만들어진 자료 구조이다. 시간 복잡도 : O(logN)

여러 개의 값들 중에서 max 혹은 min value를 빠르게 탐색하기 위해서 만들어졌다. 

중복된 값을 허용하지 않는 일반적인 complete binary tree와는 달리 heap tree에서는 중복된 값을 허용한다. 

 

heap의 기본 속성 : A가 B의 부모 노드라면, A의 key value와 B의 key value에는 대소 관계가 성립하며, 해당 대소관계는 heap의 종류에 따라서 달라진다. 

 

종류

 

1) Max Heap : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 complete binary tree

2) Min Heap : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 complete binary tree

 

구현

heap을 구현할 때는 보통 list (array) 자료 구조를 사용한다.

구현의 편의를 위해서 보통 첫번째 Index는 사용하지 않으며, 새로운 노드가 추가된다고 해서 각 노드의 번호가 변경되지는 않는다.

 

부모 노드와 자식 노드의 Index 관계

왼쪽 자식 노드의 Index : 부모 노드의 index * 2

오른쪽 자식 노드의 index : 부모 노드의 index * 2 + 1

부모 노드의 index : 자식 노드의 index / 2

 

연산

insertion (삽입) : heap 에 새로운 요소가 들어오며느 새로운 노드를 힙의 마지막 노드에 추가하여, 삽입을 해둔다. 새로운 노드를 부모 노드들과 비교하며 힙의 성질에 따라 교환 해 나간다. 

 

 

deletion (삭제) : max heap에서의 deletion 연산을 생각해보자. max heap에서 max value는 root node이므로, root node를 삭제한다. 삭제된 root node에는 heap의 마지막 node를 일단 가져다 놓는다. heap의 성질에 따라서 비교하며 재구성한다.