자료구조 : Heap

Heap

여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
heap은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 또한 중복된 값을 허용한다. (이진 트리 탐색에서는 중복된 값을 허용하지 않는다.)
힙에서는 항상 루트 노드를 제거한다.

반정렬 상태
완전 이진 트리 구조에서 부모 노드와 자식 노드 사이의 정렬만 보장되고 형제 노드 간의 정렬은 보장되지 않는 상태

Heap의 종류

Max heap

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 루트 노드가 가장 큰 값을 가지기 때문에 이 데이터가 우선적으로 제거됨.
• key(부모 노드) >= key(자식 노드)

Min heap

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• 루트 노드가 가장 작은 값을 가지기 때문에 이 데이터가 우선적으로 제거됨.
• key(부모 노드) <= key(자식 노드)

최소 힙 구성 함수 : Min-Heapify()

• (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.
• 새로운 원소가 삽입되었을때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

---

Heap 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위해서 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

---

Heap의 삽입

1. heap에 새로운 요소가 들어오면, 일단 새로운 노드를 heap의 마지막 노드에 이어서 삽입
2. 새로운 노드를 부모 노드들과 교환해서 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

---

Heap의 삭제

1. 최대 힙에서의 최댓값은 루트 노드이므로 루트 노드가 삭제됨.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성 한다.

# 삭제 과정
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))

Heap 내장 모듈(heapq)

from heapq import heappush, heappop

heapq 모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와준다.
PriorityQueue 클래스처럼 리스트와 별개의 자료구조가 아닌 점에 유의해야 한다.
파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙이다.

• 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

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

heappush(heap, (-num, num)) 튜플 (-num, num)이 핵심이다.
큰 수일 수록 -가 붙어 힙 구조에선 양수일때와 반전된 결과가 기재되어진다.