[Algorithm] 이진 힙 Binary Heap

이진 힙이란?

이진힙은 우선 순위 큐를 위해서 만들어진 완전 이진 트리의 한 종류이다. 즉, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조다. 이진 힙은 힙 중에서 가장 널리 쓰이며 힙의 특징(ex. 최대힙의 경우 부모 노드는 자식 노드보다 값이 커야 한다)을 만족한다. 참고로 이진 탐색 트리에서는 중복된 값을 허용하지 않지만, 힙 트리에서는 중복된 값을 허용한다.

 

 

종류

• 최대 힙 max heap: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙 min heap: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

구현

• 일반적으로 배열을 이용해서 구현한다.
• 구현을 쉽게 하기 위해서 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 너드 번호는 새로운 노드가 추가되어도 변하지 않는다.
• 힙에서 부모 노드와 자식 노드의 관계는 다음과 같다.
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

• 삽입 O(logn)
  • 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
  • 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
• 삭제
  • 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
  • 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
  • 힙을 재구성한다.

힙 정렬

힙에서 자료를 꺼낼 때 가장 큰/작은 값부터 나오는 성질을 이용한 정렬. 힙에 자료를 하나 넣을 때 평균 O(logn)의 복잡도를 가지며 이를 n번 반복하기 때문에 전체 복잡도는 O(nlong)이 된다. 퀵 정렬과 평균 시간 복잡도는 동일하지만 퀵 정렬이 최악의 경우 O(n^2)가 나오는 것에 비해 언제나 O(nlong)을 넘지 않기 때문에 장점이 된다.

---

Reference

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://kayuse88.github.io/binary-heap/