힙(Heap)

• 가장 높은(낮은) 우선순위를 가지는 노드를 빠르게 찾아내기 위해 고안된 완전 이진 트리(Complete Binary Tree)(노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리)기반의 자료구조

• 가장 높은(낮은) 우선순위를 가지는 노드가 항상 루트 노드(root node)에 오는 것이 특징

---

힙 구조

• 힙은 최대값을 구하기 위한 구조와 최소값을 구하기 위한 구조로 분류

• 최대 힙(Max Heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

• 최소 힙(Min Heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

---

힙을 사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 $O(n)$이 걸리나,
  힙에 데이터를 넣고 최대값과 최소값을 찾으면 $O(log_n)$이 걸림
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

---

힙과 이진 탐색 트리의 공통점 및 차이점

• 공통점

  • 힙과 이진 탐색 트리는 모두 이진 트리 구조

• 차이점

  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음 (Max Heap의 경우)

  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 부모 노드, 오른쪽 자식 노드 값이 가장 큼

  • 힙은 이진 탐색 트리와 다르게 자식 노드의 작은 값이 왼쪽 그 다음 오른쪽에 들어가야 한다는 조건이 없음

  • 이잔 탐색 트리는 탐색을 위한 구조 / 힙은 최대,최소값을 찾기 위한 구조

---

힙 동작 방식

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

• 채워진 노드 위치에서 부모 노드 보다 값이 클 경우, 부모 노드와 위치를 바꿔줌

• 일반적인 삭제의 경우 최상단 노드(root node)를 삭제하는 것이 일반적

• 상단의 노드를 삭제시, 가장 최하단부 왼쪽에 위치한 노드를 root node로 이동

• root node의 값이 자식 노드 보다 작을 경우, root node의 자식 노드 중 가장 큰 값을 가진 노드와 root node 위치를 바꿈

---

코드 구현

참고 블로그