1. 힙(Heap)이란 ?
힙(Heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻
- 완전 이진 트리의 형태를 띄는 자료구조
- 완전 이진트리는 노드를 삽입할때 왼쪽부터 차례대로 삽입하는 트리.
- 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
- 최댓값 혹은 최솟값을 O(1)안에 찾을 수 있음.
- 데이터 삽입, 삭제의 경우 O(log N)이 소요됨.
- 부모노드와 자식노드 사이에 항상 대소관계가 성립한다. (최대 힙, 최소 힙)
- 형제노드 사이에는 대소관계가 정해지지 않음.
- 대부분 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 대부분 사용
- 힙을 응용하여 우선순위 큐 같은 자료구조를 구현 할 수 있다.
2. 힙의 종류
| 구분 | 최대 힙(max heap) | 최소 힙(heap) |
|---|---|---|
| 크기 | 부모노드 >= 자식노드 | 부모노드 <= 자식노드 |
| 루트 | 최대 값을 가짐 | 최소 값을 가짐 |
3. 힙의 구현
힙의 표준 자료구조는 배열(Array) 이다.
📌 대게 인덱스는 계산의 편리함을 위해 1번부터 시작함.
- 왼쪽 자식의 인덱스 = (부모의 인덱스) *2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) *2+1
- 부모의 인덱스 = (자식의 인덱스)/2
힙에 데이터의 삽입 삭제가 일어나게 되면 힙 트리의 조건이 깨지기 때문에 노드들의 위치를 바꿔서 재구조화(heapify) 해주어야 한다. 원소 하나가 추가되면, 부모와 자식의 값을 비교하여 바꾸어주면서 최대힙/최소힙을 만드는 과정을 반복한다.
따라서 삽입, 삭제자체는 O(1)이지만, 재구조화 과정에서 O(log N)의 시간복잡도를 가진다.
3-1. 데이터의 삽입
1️⃣ 가장 끝의 자리에 노드삽입.
2️⃣ 해당 노드와 부모 노드를 서로 비교한다.
3️⃣ 규칙에 맞지 않으면 부모와 교환한다.
4️⃣ 규칙에 맞을 때까지 반복, 맞으면 교환을 끝낸다.
3-2. 데이터의 삭제
힙에서 삭제는 최댓값/최솟값이 저장된 루트 노드만 제거할 수 있다.
1️⃣ 루트 노드 제거.
2️⃣ 루트 자리에 가장 마지막 노드 삽입.
3️⃣ 올라간 노드와 그의 자식 노드와 비교.
4️⃣ 조건에 만족할때 까지 자식노드와 교환.
4. 힙 정렬 (Heap Sort) 알고리즘
- 최대 힙 트리 또는 최소 힙 트리를 구성해 정렬을 하는 알고리즘
- 힙 정렬의 시간복잡도는 O(n log n)
- 구현 과정
참고 자료 (Reference)
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap
https://velog.io/@chappi/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-5%EC%9D%BC%EC%B0%A8-Onlogn-%EC%A0%95%EB%A0%AC-%ED%9E%99%EA%B3%BC-%ED%9E%99%EC%A0%95%EB%A0%AC-%EC%B5%9C%EB%8C%80%ED%9E%99-%EC%B5%9C%EC%86%8C%ED%9E%99-2%EB%B6%80
