Data Structure(4) Heap(힙)

맨 처음에 힙을 들었을 때 엉덩이(hip)가 생각날 수도 있지만 힙은 heap이다.

무언가를 차곡차곡 쌓아 올린 더미라는 뜻이라고 한다.

 

그렇다면 힙(heap)이란 무엇인가요? 🤷‍♂️

1. 힙(heap)은 완전 이진트리의 형태로 만들어져 있고, 우선순위 큐를 위하여 만들어진 자료구조이다.

2. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

3. 힙(heap)은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.

4. 힙 트리는 중복 값을 허용한다.

5. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다.(아래 사진 참조)

* 완전 이진트리란? 

* 마지막을 제외한 모든 노드의 자식들이 꽉 채워진 이진트리이다.

 

힙(heap)의 종류

---

최대 힙(max heap)

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

* key(부모 노드) >= key(자식 노드)

 

최소 힙(min heap)

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

* key(부모 노드) <= key(자식 노드)

최대 힙, 최소 힙

 

힙(heap)의 구현

---

힙을 저장하는 표준적인 자료구조는 배열이다.

구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

 

 

 

부모 노드와 자식 노드의 관계

예를 들어 위에 그림에서 루트 노드의 오른쪽 노드의 번호는 항상 3이다.

 

힙에서 부모 노드와 자식 노드의 관계

왼쪽 자식의 인덱스(leftChild) = (부모의 인덱스) * 2

오른쪽 자식의 인덱스(rightChild) = (부모의 인덱스) * 2 + 1

부모의 인덱스(parent) = (자식의 인덱스) / 2

 

위에 부모 노드와 자식 노드의 관계를 이해했다면 👍

이해 못했다면 다시 보자

왼쪽 자식 구하는 방법 => (자신의 인덱스) * 2 => 1 * 2 = 2

오른쪽 자식 구하는 방법 => (자신의 인덱스) * 2 + 1 = 1 * 2 + 1 = 3

부모 인덱스 구하는 방법 => (자식의 인덱스) / 2 

 

 

힙(heap)의 연산

---

아래 연산들은 최대 힙(max heap)을 기준으로 설명해보려 한다.

 

힙(heap)의 삽입(insert) 연산

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.

2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

* 아래 최대 힙(max heap)에 새로운 요소 8을 삽입하는 사진을 이해해보자.

힙(heap)의 삽입 연산

 

위에 사진을 이해했다면 8의 값이 아니고, 5, 6, 10의 값이 들어와도 힙(heap)의 구조를 그릴 수 있다면 성공이다.

 

힙(heap)의 삭제(delete) 연산

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다. 

* 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.

2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.

3. 힙을 재구성한다.(heapify)

* 아래의 최대 힙(max heap)에서 최댓값을 삭제해보자.

힙(heap)의 재구조화(heapify)

힙에서 원소의 삽입이나 삭제가 일어나면 최대 힙의 조건이 깨질 수 있다.

이 경우 다시 최대 힙의 조건을 만족하도록 노드의 위치를 바꾸는 것을 재구조화(heapify)라고 한다.

 

삽입과 삭제의 경우 연산 자체는 O(1)의 시간 복잡도로 작동하지만, 재구조화(heapify)의 과정이 O(logN)이기 때문에 최종적으로 O(logN)의 시간 복잡도를 가지게 된다.

 

힙 만들기(build heap)

build heap은 힙이 아닌 배열을 힙으로 만드는 과정이다. 이때 heapify를 N번 진행하게 되므로 시간 복잡도는 O(NlogN)이다.

 

<build heap 과정>

가장 말단의 오른쪽에 있는 노드의 부모 노드부터 위에서 아래로 heapify를 진행한다. 

 

힙 정렬(heap sort)

힙 정렬은 추가적인 배열을 사용하지 않고 시간 복잡도 O(NlogN)에 수행 가능하다.

 

* 내림차순 정렬 -> 최대 힙 사용

* 오름차순 정렬 -> 최소 힙 사용

 

힙 정렬은 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때 가장 유용하다.

만약 10개 원소 중에서 가장 큰 값 3개만 알고 싶다면, 최대 힙을 구성한 다음 가장 큰 값(루트 노드)을 3번 삭제하며 값을 확인하면 된다. 

 

<힙 정렬 과정>

1. 정렬할 N개의 원소로 최대 힙 구성

2. 최대 힙의 루트 노드(가장 큰 원소)와 마지막 원소 위치 교환

3. 새 루트 노드에 대해 최대 힙 구성

4. 원소 개수만큼 2와 3을 반복 수행

 

과정 1은 앞에서 살펴본 build heap 과정으로 O(NlogN)의 시간 복잡도를 가진다. 

과정 2와 3은 최대 힙에서 원소를 하나 삭제한 다음 heapify를 진행하는 것과 같으므로 O(logN)이 걸린다.

이 과정이 원소의 개수만큼 반복되므로 결국 O(NlogN)의 시간 복잡도를 가진다.

 

 

+ 번외
우선순위 큐를 구현하는 방법(시간 복잡도)

 

출처 : https://mjmjmj98.tistory.com/154

 

Reference

• 힙(heap)이란?(1)
• 힙(heap)이란(2)
• 힙(heap)이란?(3)
• 힙 정렬(Heap Sort)
• 그림으로 보는 힙(Heap)