heapq

힙의 구조

min heap 기준의 정렬방법:
1. 값을 하나씩 트리의 노드에 좌에서 우로 할당
2. 부모노드의 값이 자식 노드보다 크면 부모와 자식을 교체
3. 루트노드까지 비교를 반복

출처:https://redcrow.tistory.com/487

힙에 원소 추가

heapq.heappush(리스트, 넣을값)

heap = []
1. heapq.heappush(heap, 4)
2. heapq.heappush(heap, 1)
3. heapq.heappush(heap, 7)
4. heapq.heappush(heap, 3)

1. 부모노드 = 4
2. 자식 왼쪽 노드에 1 추가 -> 부모노드보다 값이 작으므로 부모노드와 자리 전환
3. 자식 오른쪽 노드에 7추가
4. 자식 왼쪽 노드의 자식노드에 3추가 -> 부모노드인 4보다 값이 작으므로 부모노드와 자리전환

heap = [1, 3, 7, 4]

힙에 원소 삭제

heapq.heappop(heap)

heap = [1, 3, 7, 4]
print(heapq.heappop(heap))
print(heap)

1. heap의 가장 작은수 1을 뺌
2. heap중 가장작은 3이 제일 위의 부모노드에 위치
3. 왼쪽 자식노드 자식에 위치하던 4는 왼쪽 자식노드로 위치

1 #print(heapq.heappop(heap))
[3, 4, 7] (heapq.heappop(heap))

기존리스트 힙으로 변환

heapq.heapify(list)

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

힙의 문법에 맞게 숫자가 배치됨

응용

1. 오름차순 정렬

heap = [4,1,7,3,8,5]
sort_heap = []
heapq.heapify(heap)
while heap:
    sorted_heap.append(heapq.heappop(heap))
    print(sorted_heap)

주의할점:
꼭 heapq.heapify를 해주거나 heappush를 이용하여 리스트 heap을 heap구조로 만들어주어야 한다.
그렇지 않을 경우 heappop을 하였을때 가장 작을 수를
빼지 못한다.
이유: 보통의 리스트는 순서대로 index번호가 정해지기 때문

2. 내림차순 정렬

튜플이용하기

nums = [4,1,7,3,8,5]
  heap = []
  for num in nums:
      heapq.heappush(heap, (-num,num)) #(정렬기준, 값)
  /
  while heap:
      print(heapq.heappop(heap)[1],end =' ')
      #8 7 5 3 1

• -num값을 주어서 가장 큰수를 가장 작게 만들어주는 방법

3. 최대값과 최솟값을 구하는 방법

heapq.nlargest(n, iterable, key=None)
heapq.nsmallest(n, iterable, key=None)

 import heapq
>> nums = [1, 3, 6, 34, 5, 22, 67, -3, 56, -9]
>> print(heapq.nlargest(5, nums))
[67, 56, 34, 22, 6]

nums에서 큰 순서대로 5개 만큼 나오는 것을 알 수 있다.