heap이란

1) 정의

데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 내장 모듈

• min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치합니다.
• 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제됩니다.

heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]

예를 들어, 아래 그림은 위 공식을 만족시키는 간단한 min heap의 구조를 보여주고 있습니다.

     1  ---> root
   /   \
  3     5
 / \   /
4   8 7

2) 모듈 사용하기

• 모듈 import

from heapq import heappush, heappop

• heap 생성

heap = []

heappush(heap,4)
heappush(heap,1)
heappush(heap,7)
heappush(heap,3)
heappush(heap,8)
heappush(heap,5)

print(heap)
▶
[1, 3, 5, 4, 8, 7]

• heap에 원소추가
  heap은 이진 트리이며 부모 노드는 반드시 자식 노드보다 작아야 한다.
  키값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 없다.

  heappush vs append
  heappush는 추가해줄 때마다 heap 정렬이 자동으로 진행
  append는 맨 뒤에 원소 추가

heap = [1, 3, 5, 4, 8, 7]
heap.append(0)
print(heap)
▶
[1, 3, 5, 4, 8, 7, 0]

heap = [1, 3, 5, 4, 8, 7]
heappush(heap,0)
print(heap)
▶
[0, 3, 1, 4, 8, 7, 5]

• heap에서 원소 삭제

print(heappop(heap))
▶
1
print(heap)
▶
[3, 4, 5, 7, 8]

print(heappop(heap))
▶
3
print(heap)
▶
[4, 7, 5, 8]

print(heappop(heap))
▶
4
print(heap)
▶
[5, 7, 8]

• 최소값 삭제하지 않고 접근하기
  - index = 0 에는 최소값이 있지만 그 뒤로 정렬은 아님

heap = []

heappush(heap,4)
heappush(heap,1)
heappush(heap,7)
heappush(heap,3)
heappush(heap,8)
heappush(heap,5)

print(heap)
▶
[1, 3, 5, 4, 8, 7]

print(heap[0])
▶
1

heappush(heap, 1)
print(heap[0])
▶
1

print(heap)
▶
[1, 3, 1, 4, 8, 7, 5]

• 기존 리스트 힙으로 변환
  - heapify 사용 시 원본을 변경 시킨다.
  - heapify는 return 값이 없는 함수이다. a = heapify(a) => a=None
  

from heapq import heapify

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

nums = [4,1,7,3,8,5]
heap = nums[:]
heapify(heap)
print(heap)
▶
[1, 3, 5, 4, 8, 7]

print(nums)
▶
[4, 1, 7, 3, 8, 5]

3) heap 모듈 응용

• 최대 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(heap)
    print(heappop(heap)[1])
▶
[(-8, 8), (-7, 7), (-5, 5), (-1, 1), (-3, 3), (-4, 4)]
8
[(-7, 7), (-4, 4), (-5, 5), (-1, 1), (-3, 3)]
7
[(-5, 5), (-4, 4), (-3, 3), (-1, 1)]
5
[(-4, 4), (-1, 1), (-3, 3)]
4
[(-3, 3), (-1, 1)]
3
[(-1, 1)]
1

• n번째 최소값/최대값(알고리즘)

from heapq import heappush, heappop, heapify

def nth_smallest(nums, n):
    heap = []
    for num in nums :
        heappush(heap, num)
    # heap = nums[:]
    # heapify(nums)    heapify로 한번에 가능


    nth_min = None
    for _ in range(n):
        nth_min = heappop(heap)

    return nth_min
    
print(nth_smallest([4,1,7,3,8,5],3))
▶
4

• n번째 최소값/최대값(함수)

from heapq import nsmallest, nlargest

print(nsmallest(3, [4,1,7,3,8,5]))  # list를 인자로 받음
▶
[1, 3, 4]

print(nlargest(3, [4,1,7,3,8,5]))
▶
[8, 7, 5]

• 힙 정렬

from heapq import heappush, heappop

def heap_sort(nums) :
    heap = []
    for num in nums :
        heappush(heap, num)

    sorted_nums = []
    while heap:
        sorted_nums.append(heappop(heap))

    return sorted_nums

heap_sort([4,1,7,3,8,5])
▶
[1, 3, 4, 5, 7, 8]