힙(Heap)이란?

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조

최댓값과 최솟값이 빠르게 알아내기 위한 목적으로 사용되는 자료구조!

어디에 사용하는데??

일반적인 큐는 리스트 형태를 가지고 있기 때문에 원소의 최대/최소를 찾기 위해서는 O(N)이라는 시간복잡도가 발생한다.

하지만 힙을 사용하여 우선순위 큐를 나타내면 원소의 최대/최소를 찾기위해 O(logN)이라는 시간복잡도가 발생한다.

이는 힙의 최대/최소 탐색은 이진탐색트리를 통해 최대/최소의 원소를 찾는 작업과 같기 때문이다.

(이진 탐색 트리는 왼쪽 자식은 더 작은 값, 오른쪽 자식은 더 큰 값으로 이루어져 있기에 힙과 배치 차이는 있음)

아무튼, 이러한 이유로 우선순위 큐는 대부분 힙으로 많이 구현한다.

힙에서 알아내야 할 요소가 최대 / 최소이므로, 최대를 기준으로 한 힙과 최소를 기준으로 한 힙으로 나눌 수 있다.

이를 최대힙(Max heap)과 최소힙(Min heap)이라고 한다.

최대힙은 루트노드를 가장 큰 값으로 하며, 부모 노드의 자식들을 부모노드보다 작은 값으로 주어지며 연결된다.

반대로, 최소힙은 루트노드를 가장 작은 값으로 하며, 부모노드의 자식들은 부모노드보다 큰 값으로 주어지며 연결된다.

힙을 코드상에서 어떻게 구현할까?

필자는 리스트를 이용해서 구현하는 것을 좋아함.

즉, 트리의 규칙을 이용하여 트리를 리스트화 하는 것이다.

트리를 리스트로 구현했을 때의 규칙은 다음과 같다.

부모 노드의 인덱스 = 자식 노드의 인덱스 // 2
왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1

이제 이 규칙을 사용해서 위에 있는 힙의 그림을 코드로 나타내보자!

max_heap = [None, 14, 8, 11, 1, 4]
min_heap = [None, 1, 4, 8, 11, 14]

여기서 0번째 인덱스를 None으로 놓은 이유는 사용하지 않는다는 것을 표시하기 위함이다.

0번째를 루트 노드로 사용하면 -1을 해줘야 하는 번거로움이 존재해서 잘 사용하지 않는 편이다.

힙에서 삽입 또는 삭제 시 유의사항이 있다.

바로, 경우에 따라 최대힙 또는 최소힙의 조건이 깨질 수 있다는 것이다.

이런 경우에는 노드들의 위치를 바꿔가며 힙을 재구조화(heapify) 해주어야 한다.

따라서, 단순한 삽입/삭제는 O(1)이지만, heapify의 과정을 거치기에 결국 O(logN)의 시간복잡도를 가지게 된다.