[자료구조] 힙(Heap)

힙이란?

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리

최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다.
하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다.

구현

힙의 구현은 주로 배열로 진행한다.

• 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
  예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
• 힙에서의 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

 

최대 힙과 최소 힙

• 최대 힙은 자식 노드 보다 부모 노드의 값이 크다 → 루트 노드의 값이 가장 크다.
• 최소 힙은 자식 노드 보다 부모 노드의 값이 작다 → 루트 노드의 값이 가장 작다.
• 노드가 왼쪽부터 채워지는 완전 이진 트리 형태를 가진다.
• 중복을 허용한다.

 

추가와 삭제

값을 추가할 땐 트리의 맨 마지막에 추가하고, 값을 삭제할 땐 루트노드를 삭제한 후 마지막 노드를 루트에 올려둔다.

이후 힙의 조건에 맞도록 옮긴 노드를 부모 혹은 자식 노드와 비교하며 바꿔준다.

예시는 최대 힙이라고 생각하고 진행한다.

값 추가

1. 새로운 노드를 트리의 맨 뒤에 추가한다. (완전 이진 트리의 형태를 깨면 안됨)
2. 추가된 노드와 부모 노드를 비교하여 자식 노드가 크다면 서로의 위치를 바꾼다.
3. 2번 작업을 부모 노드가 더 클때까지 반복한다.

예시

• 새로운 값 50을 가장 마지막에 추가한다.(완전이진트리를 깨면 안되기 때문에, 왼쪽 노드부터 채운다)

• 50의 부모 노드의 값 13과 비교한다.

 

• 50이 더 크기 때문에, 13과 자리를 바꾼다. 이후 현재 50의 부모노드인 44와 비교한다.

• 44보다 50이 크므로 한번 더 바꾼다. 해당 위치의 부모 노드인 55와 비교하니 55가 더 크다. 조건을 맞췄으니 그대로 유지한다.

진행 과정은 위와 같다. 자료를 추가할 때의 시간 복잡도는, 가장 많이 비교하는 경우 == 트리의 높이 이다.

마지막 레벨까지 꽉 찬 포와 이진 트리에서 트리의 높이는 $log(n+1)$ 이기 때문에, 시간 복잡도는 $O(logN)$ 이다.

값 삭제

다음으로는 자료의 삭제이다. 자료가 삭제되는 경우는 맨 위에있는 Root노드가 빠지는 경우밖에 없다. 그렇게되면 다시 힙의 형태를 갖추어야한다.

1. 맨 뒤에있는 노드를 Root자리로 옮긴다.
2. 자식 노드중 값이 더 큰 노드와 비교하여 자식 노드가 값이 더 크다면 위치를 바꾼다.
3. 2번의 작업을 자식노드보다 자신이 클때까지 반복한다.

예시

• 해당 트리에서 55를 제거한다.

• 맨 마지막에 있는 노드 10을 루트에 가져온다.

• 루트로 올린 후 자식들과 비교하는데, 자식 둘 중 44가 더 크므로, 44와 비교한다. 44가 더 크므로 자리를 바꾼다.

• 자리를 바꾼 후, 다시 자식노드와 비교하는데, 자식노드 중 더 큰 13과 비교한다. 13이 더 크므로 자리를 바꾼다.

• 힙의 구조를 유지할 수 있게 되었다.

값의 삭제 역시 트리의 높이가 가장 많은 비교 횟수와 같기 때문에, $O(logN)$ 의 시간복잡도를 가진다.

위처럼 자료를 추가/삭제한 이후 다시 힙 형태로 수정하는 과정을 Heapify 라고 한다.

---

참고 레퍼런스

[자료구조] 힙(Heap) 이해하기

[자료구조] 힙(heap)이란 - Heee's Development Blog

[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)