heap

힙(heap)

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료 구조

최대 힙 (max heap)

• 키 값이 가장 큰 노드를 찾기 위한 힙
• 부모 노드의 키 값 > 자식 노드의 키 값
• 루트 노드 = 키 값이 가장 큼

최소 힙 (min heap)

• 키 값이 가장 작은 노드를 찾기 위한 힙
• 부모 노드의 키 값 < 자식 노드의 키 값
• 루트 노드 = 키 값이 가장 작음

특징

• 힙은 무조건 완전 이진 트리
• 무조건 루트 데이터만 본다 !
• 형제끼리는 정렬되어있지 않다

힙 연산 - 삽입

: 일단 마지막에 집어넣은 후 바꾸자

• 연산 횟수 : logN (항상 트리의 높이만큼 바뀌니까)

힙 연산 - 삭제

• 힙에서는 루트 노드의 원소만을 삭제할 수 있다

• 루트 노드의 원소를 삭제하여 반환한다
  

• 연산 횟수 : logN

=> 힙은 삭제,삽입 모두 logN을 보장한다 (완전 이진 트리니까)

힙의 활용

• 대표적으로 우선순위 큐의 구현과 정렬에서 힙을 활용한다.

• 우선순위 큐를 구현하는 가장 효율적인 방법이 힙을 사용하는 것.

  • 노드 하나의 추가/삭제 시간 복잡도 : O(logn)
  • 최대/최소 찾기 : O(1)

• 힙 정렬 : O(nlogn) 보장

heapq.heapify

heapq.heapify() 는 리스트를 “힙(heap) 자료구조”로 바꿔주는 함수이다. 파이썬 heapq 는 기본적으로 최소 힙(min heap) 구조를 사용한다.

import heapq

lst = [5, 3, 8, 1, 2]
heapq.heapify(lst)

print(lst)

• 일반 리스트를 힙 구조로 재정렬
• 시간복잡도 O(N)
• 힙의 특징: 부모 ≤ 자식 (최소 힙)

예시 결과 : [1, 2, 8, 3, 5]
정확히 이 순서는 아닐 수 있지만, lst[0] == 최소값 임을 보장한다.

최대 힙을 만들고 싶으면 음수로 바꿔서 집어넣어준 후, 꺼낼 때 다시 음수를 곱해준다

heapq 알아줘야 할 함수

1. heapify

• 리스트를 힙으로 변환

heapq.heapify(lst)

2. heappush

• 힙에 값 추가

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

print(heap)

3. heappop

• 최소값 제거 + 반환

heapq.heappop(heap)

4. 최대 힙 만들기

heap = []

heapq.heappush(heap, -5)
heapq.heappush(heap, -1)
heapq.heappush(heap, -3)

print(-heapq.heappop(heap))

우선순위 큐 (Priority Queue)

• 값을 넣은 순서가 아닌 우선순위가 높은 것부터 먼저 꺼내는 큐 이다.

• 파이썬에서는 보통 heapq(힙)으로 구현한다.

import heapq

pq = []

heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 5)

print(heapq.heappop(pq))

• 첫 번째 값을 기준으로 정렬한다

heap = []

heapq.heappush(heap, (cost, node))

heapq.heappush(heap, (3, "A"))
heapq.heappush(heap, (1, "B"))
heapq.heappush(heap, (2, "C"))

print(heapq.heappop(heap)) // (1,'B') 

• 삽입/삭제 O(logN)
• 최소값 확인 O(1)