[Data Structure] 힙 (Heap)

힙 (Heap) ?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
- 완전 이진 트리 : 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

 

힙을 사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 <--시간복잡도
• 이에반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면, O(logn)이 걸림
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 활용

 

 

힙(Heap) 구조

• 힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와, 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음
• 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
  2. 완전 이진 트리 형태

 

힙  vs  이진탐색트리

• 공통점 : 둘다 이진 트리
• 차이점
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
  • 이진 탐색 트리는 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드의 값
  • 힙은 이진탐색트리의 조건인 값의 크기에 따른 위치 조건이 없음
• 목적
  • 이진 탐색 트리 : 탐색을 위한 구조
  • 힙 : 최대/최소값 검색을 위한 구조

Heap vs Binary Search Tree