Heap(힙)에 대하여

Heap(힙)

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다.
• 여러 개의 값중에 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다.
• 힙은 반정렬 상태(느슨한 정렬 상태)를 유지합니다.

 

 

[ 완전 이진 트리의 의미 ]

 

완전 이진 트리에서 완전이라는 말의 의미는 마지막 레벨을 제외한 모든 노드가 채워져 있으면서

모든 노드가 왼쪽부터 채워져 있어야 하는 것을 의미합니다. 

 

위 그림에서 완전 이진트리는 마지막 레벨을 제외한 모든 노드가 채워져 있고 왼쪽부터 채워진 형태를

볼 수 있습니다.

 

만약 마지막 레벨의 노드가 모두 채워져 있으면 이를 포화 이진트리라고 부르게 됩니다.

 

 

 

[ 힙의 반정렬(느슨한 정렬) 상태 ]

 

힙은 어떻게 최댓값 또는 최솟값을 빠르게 찾아낼 수 있을까요?

힙이 아닌 리스트에 특정 값을 넣고 우선순위가 높은 것 부터 빼려고 한다면 정렬을 하게 됩니다.

정렬을 하려면 새 원소가 들어올 떄 마다 이미 리스트에 있는 여러 원소들과 비교를 해야합니다.

 

이것은 비효율적이기 때문에 힙은 부모 노드는 항상 자식 노드 보다 우선순위가 높다는 조건을

활용하여 이진 트리를 채워나갑니다.

 

즉 새로운 값을 힙에 넣게 되면 모든 노드들을 비교하는 것이 아니라 부모 노드만 비교를 하면 됩니다.

다시 말하자면 모든 노드들의 부모 격인 루트 노드는 항상 우선순위가 높은 노드가 됩니다.

 

여기서 발생하는 특징이 힙은 부모노드와 자식노드의 관계만 신경쓰기 때문에 형제 노드끼리의 비교는

하지 않게 됩니다. 이로 인해 모든 노드들이 정렬된 상태가 아닌 '반 정렬 상태' 혹은 '느슨한 정렬 상태'가 

됩니다. 

 

형제 노드간의 대소 비교가 필요 없는 이유는 힙 자체가 우선순위가 높은 순서대로 뽑기 위해 구현된

자료구조이기 때문입니다. 루트 노드가 모든 노드보다 우선순위가 높다면 굳이 그 밑에 있는 노드들이

우선순위에 맞게 정렬 되어있는지 확인할 필요가 없습니다. 자식 노드와 부모 노드의 관계 비교를 통해

루트 노드는 우선순위가 제일 높게 되기 때문에 형제 노드들 간의 비교는 필요 없게 됩니다.

 

 

---

힙의 구현

 

힙을 저장하는 표준적인 자료구조는 배열입니다.힙은 완전 이진 트리이기 때문에 왼쪽 부터 오른쪽으로

차곡차곡 노드가 저장되게 됩니다. 따라서 배열의 구조를 사용할 수 있습니다.

 

구현의 편의성을 위해 배열의 첫번째 인덱스 0은 사용하지 않습니다.

또한 배열이기 때문에 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않습니다.

 

최대 힙을 배열로 표현하면 위 그림과 같습니다. 0번 인덱스는 사용하지 않은 것을 알 수 있습니다.

여기서 부모노드와 자식노드 간의 규칙을 몇 가지 발견 할 수 있습니다.

 

부모 노드 Index  =  자식 노드 Index  / 2

왼쪽 자식 노드 Index  = 부모 노드 Index * 2

오른쪽 자식 노드 Index = (부모 노드 Index * 2) +1 

 

위 규칙을 활용하여 힙의 삽입 및 삭제 시에 부모 노드와 자식 노드를 손쉽게 배열에서 구할 수 있게 됩니다.

 

 

 

---

힙의 동작 과정

조건 - 값이 높을 수록 우선순위가 높다는 조건하에 동작합니다! (최대 힙 가정)

 

 

[ 삽입 과정 ]

 

1. 가장 말단 노드에 삽입

2. 부모 노드와 비교하여 자식 노드가 우선순위가 높다면, 둘의 자리를 교환!

3. 바뀐 자리에서 자신의 부모 노드와 우선순위 비교! 우선순위가 높으므로 둘의 자리를 교환

4. 다시 한번 부모노드와 우선순위 비교, 우선순위가 높으므로 교환!

 

 

다음과 같이 삽입 과정은 트리의 말단 노드에 값을 삽입하고 부모노드를 찾아가면서 요소를 교환하며 올라가게 됩니다.

이를 위로 올라가면서 선별한다하여 상향 선별(sift-up) 이라고 부르기도 합니다.

 

 

 

 

 

 

[ 삭제 과정 ]

 

힙을 삭제하면 우선 순위가 제일 높은 루트 노드가 삭제됩니다. 루트 노드가 삭제 되면 말단 노드를 루트노드 자리에 대체한 후 재구조화 작업이 수행됩니다. 동작과정은 밑에 그림과 같습니다.

 

1. 루트 노드를 삭제 한 후에 마지막 원소를 루트로 이동

 

2. 2개의 자식 노드 중 우선순위가 더 높은 자식 노드와 위치를 교환

3. 교환된 노드에서 다시 큰 값을 지닌 자식 노드와 위치를 교환

4. 또 다시 큰 값을 지닌 자식 노드와 교환

다음과 같이 마지막 노드를 root노드로 가져온 다음 자식 노드와 비교하면서 자리를 찾아가게 됩니다. 이렇게 아래로 

내려가면서 재배치 하는 과정을 하향 선별 (sift-down) 이라고 부릅니다.

 

 

 

---

힙의 시간 복잡도

 

1. 힙 삽입 

최악의 경우 가장 말단에 삽입한 원소가 루트노드 까지 올라가게 됩니다. 이때 비교 횟수는 트리의 높이 만큼이 됩니다.

따라서 삽입의 시간복잡도는 O(log N)이 됩니다.

 

2. 힙 삭제 

삽입 과정과 마찬가지로 가장 최악의 경우 루트 노드에서 말단 노드까지 내려오게 되므로 비교 횟수는 트리의 높이 만큼이

됩니다. 따라서 삭제 과정은 시간 복잡도는 O(log N)이 됩니다.

 

3. 힙 정렬 

임의의 수 N개의 데이터를 힙 정렬 한다고 했을 때 차례차례 삽입을 해주면 힙 정렬이 끝나게 됩니다.

따라서 힙 정렬의 전체 시간 복잡도는 힙 삽입 시간복잡도인 O(log N)에 N을 곱한 O(N * log N)이 됩니다.

 

 

 

---

 

이상으로 힙에 대한 정리를 마치겠습니다.

 

긴 글 일어주셔서 감사합니다!

 

---

참고한 블로그

https://code-lab1.tistory.com/12#:~:text=Heap%EC%9D%80%20%EB%B0%B0%EC%97%B4%EC%9D%84%20%ED%86%B5%ED%95%B4,%EC%9D%B4%EC%A7%84%20%ED%8A%B8%EB%A6%AC%EC%9D%B4%EA%B8%B0%20%EB%95%8C%EB%AC%B8%EC%9D%B4%EB%8B%A4.

[자료구조]Max Heap, Min Heap, Heap 이란? | C언어 Heap 구현

https://sungone-develop-study.tistory.com/entry/%ED%9E%99Heap%EC%9D%98-%EA%B5%AC%EC%A1%B0%EC%99%80-%EB%8F%99%EC%9E%91%EA%B3%BC%EC%A0%95

힙(Heap)의 구조와 동작과정

https://st-lab.tistory.com/205

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기