[자료구조] 힙(Heap)이란?

힙은 트리를 기반으로 하지만 변형된 형태의 정책을 채택한다.

---

힙(Heap)

정의

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)

특징

> 힙을 이용해 최대값과 최솟값을 찾는 것은 O(logn)의 시간복잡도를 가짐 (cf. 배열 → O(n))

활용

> 우선순위 큐와 같이, 최댓값이나 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용됨

 

힙의 구조

분류

1. 최대 힙(Max Heap): 최댓값을 구하기 위한 구조
2. 최소 힙(Min Heap): 최소값을 구하기 위한 구조

조건

1. 각 노드의 값은 해당 노드가 가진 자식 노드의 값보다 크거나 같음(최대 힙의 경우) → 루트 노드가 최댓값을 가짐
2. 완전 이진 트리의 형태(노드를 삽입할 때 왼쪽 노드부터 차례대로 삽입하는 이진트리)

 

힙과 이진 탐색 트리 비교

공통점	이진 트리
차이점	힙은 각 노드의 값이 자식 노드의 값보다 크거나 작음 (최대 힙 기준) 이진 탐색 트리는 왼쪽 자식 노드의 값 < 부모 노드의 값 < 오른쪽 자식 노드의 값으로 정렬 힙은 왼쪽 자식 노드의 값 < 오른쪽 자식 노드의 값 이라는 조건을 가지지 않음

▷ 즉, 이진 탐색 트리는 탐색을 위한 구조이고 힙은 최대/최솟값 검색을 위한 구조 중 하나로 이해

 

힙과 이진 탐색 트리 비교

 

힙의 동작

데이터 삽입

1) 기본 동작

힙은 완전 이진트리이므로, 삽입할 노드는 기본적으로 최하단부의 왼쪽 노드부터 채워지는 형태로 삽입

 

 

2) 삽입할 데이터가 힙의 데이터보다 큰 경우 (최대 힙 기준)

기본 동작 후, 이동 위치에서 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함(swap)

 

 

데이터 삭제

힙의 용도에 맞게, 보통 삭제는 루트 노드를 삭제하는 것이 일반적임

 

1. 루트 노드 삭제 시, 최하단부의 가장 오른쪽에 위치한 노드를 루트 노드로 이동
2. 변경된 루트 노드의 값이 자식 노드보다 작을 경우, 루트 노드의 자식 노드 중 가장 큰 값을 가진 노드와 루트 노드 위치를 바꿔주는 작업을 반복함 (swap)