[Python] 힙 (Heap) 정리 및 구현

힙 (Heap)

 

자료구조 힙 (Heap) 이란?

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

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

 

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

\(\rightarrow\) 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다.

\(\rightarrow\) 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진 트리이다.

힙에서는 중복된 값을 허용한다.

 

힙 (Heap) 의 종류

최대 힙(max heap)

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

최소 힙(min heap)

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

---

힙 내장 모듈 heapq

 

Import

from heapq import heappush, heappop

 

heapq 모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줍니다.

PriorityQueue 클래스처럼 리스트와 별개의 자료구조가 아닌 점에 유의해야 합니다.

그렇게 때문에, 그냥 빈 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘겨야 합니다. 다시말해, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙입니다.

heappush와 heappop의 시간 복잡도는 \(O(logN)\)입니다.

 

Push

from heapq import heappush, heappop

heap = []

heappush(heap, 4)
heappush(heap, 2)
heappush(heap, 8)
heappush(heap, 1)

print(heap)
# [1, 2, 4, 8]

 

Pop

from heapq import heappush, heappop

heap = []

heappush(heap, 4)
heappush(heap, 2)
heappush(heap, 8)
heappush(heap, 1)

print(heappop(heap))
# 1
print(heap)
# [2, 4, 8]

 

기존 리스트를 힙으로 변환 heapify()

 

from heapq import heapify

heap = [4, 1, 7, 3, 8, 5]
heapify(heap)
print(heap)
# [1, 3, 5, 4, 8, 7]

 

역순으로 정렬 - 최대 힙(max heap)

힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용합니다. 따라서, 최대 힙을 만들려면 각 값에 대한 우선 순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됩니다. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됩니다. (우선 순위에는 관심이 없으므로 )

from heapq import heappush, heappop

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
	heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
	print(heappop(heap)[1])  # index 1
# 8
# 7
# 5
# 4
# 3
# 1

---

힙 (Heap) 을 배열로 구현

힙은 대체적으로 배열로 구현됩니다.

완전 이진 트리를 기본으로 하기 때문에 비어있는 공간이 없어 배열로 구현하기에 용이합니다.

 

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

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

 

각 노드를 기점으로

 

삽입과 삭제로 깨진 힙을 재구조화(heapify) 하기

최대힙의 부모 노드는 항상 자식 노드의 값보다 크다는 조건을 가지고 있습니다.

하지만 힙에서 삽입 또는 삭제가 일어나게 되면 경우에 따라 최대힙의 조건이 깨질 수 있습니다.

이러한 경우, 최대힙의 조건을 만족할 수 있게 노드들의 위치를 바꿔가며 힙을 재구조화 해주어야 합니다.

\(\rightarrow\) 삽입과 삭제의 경우 모두 연산 자체는 O(1)의 시간복잡도로 작동하지만 재구조화 과정을 거치면 \(O(\log n)\)의 시간복잡도를 가지게 됩니다.

 

삽입 과정 구현

새로운 노드는 리프 노드(Leaf Node)가 아니면서 가장 말단에 있는 노드의 자식 노드로 추가됩니다.

이후, 부모 노드와 비교하면서 재구조화 과정을 수행합니다.

삽입 과정은 아래에서 위로 재구조화 과정이 이뤄지게 됩니다.

# 삽입 과정
def up_heapify(index, heap):
    child_index = index
    while child_index != 0:
        parent_index = (child_index - 1) // 2
        if heap[parent_index] < heap[child_index]:
            heap[parent_index], heap[child_index] = heap[child_index], heap[parent_index]
            child_index = parent_index
        else:
            return

# 삭제 과정
def find_bigger_child_index(index, heap_size):
    parent = index
    left_child = (parent * 2) + 1
    right_child = (parent * 2) + 2

    if left_child < heap_size and heap[parent] < heap[left_child]:
        parent = left_child
    if right_child < heap_size and heap[parent] < heap[right_child]:
        parent = right_child
    return parent


def down_heapify(index, heap):
    parent_index = index
    bigger_child_index = find_bigger_child_index(parent_index, len(heap))
    while parent_index != bigger_child_index:
        heap[parent_index], heap[bigger_child_index] = heap[bigger_child_index], heap[parent_index]
        parent_index = bigger_child_index
        bigger_child_index = find_bigger_child_index(parent_index, len(heap))

 

삭제 과정 구현

루트 노드가 삭제되면 가장 말단 노드를 루트 노드 자리에 대체한 후 재구조화 과정을 수행합니다.

힙으로 구현된 우선순위 큐에서도 가장 우선순위가 큰 루트 노드를 주로 삭제합니다.

삽입의 경우에는 가장 말단 노드에 추가하여 재구조화 과정을 수행합니다.

# 재귀함수 힙

def up_heapify(index, heap):
    child_index = index
    while child_index != 0:
        parent_index = (child_index - 1) // 2
        if heap[parent_index] < heap[child_index]:
            heap[parent_index], heap[child_index] = heap[child_index], heap[parent_index]
            child_index = parent_index
        else:
            return

def down_heapify(array, index, heap_size):
        
        # 1. 부모노드와 자식노드들의 인덱스 지정
        parent = index
        left_child = 2 * parent + 1
        right_child = 2 * parent + 2
		
        # 2. 왼쪽 자식노드, 오른쪽 자식노드 중 가장 큰 노드를 선택
        if left_child < heap_size and array[left_child] > array[parent]:
            parent = left_child
        if right_child < heap_size and array[right_child] > array[parent]:
            parent = right_child
            
        # 3. 자식노드 중 가장 큰 노드와 부모 노드를 바꿈(배열의 값 교환)
        if parent != index:
            array[parent], array[index] = array[index], array[parent]
            
            # 4. 바뀐 자식노드의 힙을 재구조화
            make_heap(array, parent, heap_size)

def make_heap(array, index, heap_size):
        parent = index
        left_child = 2 * parent + 1
        right_child = 2 * parent + 2

        if left_child < heap_size and array[left_child] > array[parent]:
            parent = left_child
        if right_child < heap_size and array[right_child] > array[parent]:
            parent = right_child
        if parent != index:
            array[parent], array[index] = array[index], array[parent]
            make_heap(array, parent, heap_size)
	
    # 부모노드가 되는 노드들만을 골라서 뒤에서부터 heapify를 차례로 실행
    for i in range((N - 1) // 2, -1, -1):
        make_heap(array, i, heap_size)