자료구조 - Heap

Heap 힙

우선순위 큐라고도 한다. 최댓값, 최솟값의 빠른 연산을 위해 고안된 완전이진트리.

A가 B의 부모노드(Parent node)인 경우 A,B 사이에는 대소관계가 성립한다.

힙은 중복값을 허용하며 반 정렬 상태의 특성을 가진다. 

종류로는 루트값이 최대값인 최대힙과 그 반대인 최소힙이 있다.

 

힙의 연산

삽입

트리의 가장 끝 위치에 데이터를 삽입. 삽입한 키 값과 그 부모노드의 키 값을 비교하여 최대힙의 경우는 키값이 큰 경우, 최소힙의 경우는 작은 경우 부모노드와 키 값을 교체하는걸 반복한다.

연산시의 작업량이 logN 회의 형태가 되므로 시간복잡도는 O(logN)이 된다.

 

삭제

트리의 루트를 삭제한 뒤 가장 끝의 데이터를 루트와 교체한 뒤 최대힙은 자식노드중 큰 값을 가지는 키와, 최소힙은 작은 값을 가지는 키와 비교하여 정렬을 반복한다. 

역시 삽입과 같은 작업량이므로 O(logN)의 시간 복잡도를 지닌다.

 

힙의 생성

힙의 생성은 빈 힙에 삽입을 N번 반복하는 행위이므로 O(NlogN)의 시간복잡도를 지닌다.