[python] 힙(heap), 힙정렬, heapq


힙(heap)은 특정한 규칙에 따라 정렬된 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조입니다.힙은 주로 우선순위 큐(priority queue)를 구현하는 데 사용되며, 다양한 우선순위에 따라 데이터를 정렬하고 효율적으로 관리할 수 있도록 도와줍니다.

1. 힙의 특징

힙은 크게 두 종류로 나뉩니다:

  1. 최소 힙(Min Heap): 힙 내의 모든 노드의 부모 노드는 자식 노드보다 작거나 같은 값을 가집니다. 루트 노드가 최솟값을 가지게 됩니다.
  2. 최대 힙(Max Heap): 힙 내의 모든 노드의 부모 노드는 자식 노드보다 크거나 같은 값을 가집니다. 루트 노드가 최댓값을 가지게 됩니다.

힙은 다음과 같은 특징을 가지고 있습니다:

  • 삽입과 삭제가 빠르다: 최상위 노드(루트)에 접근하는 것이 빠르므로 최소값 또는 최댓값을 찾거나, 새로운 값을 삽입하거나 삭제하는데 효율적입니다.
  • 이진 트리 형태를 유지한다: 완전 이진 트리의 형태를 유지하면서 노드들이 저장됩니다.

2. 힙 정렬 구현

Python
def heapify(arr, n, i):
    largest = i  # 가장 큰 값은 현재 노드로 설정
    left_child = 2 * i + 1
    right_child = 2 * i + 2
    
    # 왼쪽 자식이 부모보다 크다면 인덱스 업데이트
    if left_child < n and arr[left_child] > arr[largest]:
        largest = left_child
    
    # 오른쪽 자식이 부모보다 크다면 인덱스 업데이트
    if right_child < n and arr[right_child] > arr[largest]:
        largest = right_child
    
    # 최대값이 자식 노드로 이동한 경우 교환
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 변경된 노드에서 재귀적으로 heapify 호출
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    
    # 최대 heap 구성
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 정렬 수행
    for i in range(n - 1, 0, -1):
        # 루트 노드(최대값)와 마지막 노드 교환
        arr[i], arr[0] = arr[0], arr[i]
        # 변경된 heap에서 다시 최대 heap 구성
        heapify(arr, i, 0)

# 테스트
arr = [12, 11, 13, 5, 6, 7]
print("정렬 전 배열:", arr)
heap_sort(arr)
print("정렬 후 배열:", arr)
#정렬 후 배열: [5, 6, 7, 11, 12, 13]

3. heapq 모듈 사용법

3.1. heapq.heappush(heap, item)

리스트 heap에 요소 item을 추가하고, heap 속성을 유지합니다.

Python
import heapq

heap = [3, 1, 5, 2, 7]
heapq.heappush(heap, 4)
print(heap)  # 출력: [1, 2, 3, 4, 7, 5]

3.2. heapq.heappop(heap)

리스트 heap에서 최소값(최상위 노드)을 추출하고 반환하며, heap 속성을 유지합니다.

Python
import heapq

heap = [1, 2, 3, 4, 7, 5]
min_value = heapq.heappop(heap)
print(min_value)  # 출력: 1
print(heap)  # 출력: [2, 4, 3, 5, 7]

3.3. heapq.heapify(x)

리스트 x를 heap 으로 변환하여 heap 속성을 유지합니다.

Python
import heapq

heap = [3, 1, 5, 2, 7]
heapq.heapify(heap)
print(heap)  # 출력: [1, 2, 5, 3, 7]

3.4. heapq.nlargest(n, iterable[, key])와 heapq.nsmallest(n, iterable[, key])

Python
import heapq

nums = [3, 1, 5, 2, 7]
largest_two = heapq.nlargest(2, nums)
smallest_two = heapq.nsmallest(2, nums)
print(largest_two)  # 출력: [7, 5]
print(smallest_two)  # 출력: [1, 2]

편안한 코딩하세요

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Scroll to Top