힙 자료구조

힙 HEAP

힙은 최소값이나 최대값을 빠르게 찾아내기 위한 트리의 일종

힙에는 최대힙과 최소힙이 있다

 

최대힙과 최소힙

Max Heap: 완전 트리이면서 ROOT가 모든 경우에 자식들보다 큰 힙(즉 최대값을 찾아내는 Heap)

Min Heap: 완전 트리이면서 ROOT가 모든 경우에 자식들보다 작은 힙(즉 최소값을 찾아내는 Heap)

 

Heap 특징

힙은 최댓값 및 최소값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리

힙 트리는 중복값을 허용한다

힙을 이용해 우선 순위 큐를 만들어낼 수 있다

 

Heap Sort의 시간 복잡도

O(logN) // 매우 빠른 정렬 알고리즘

 

파이썬을 이용한 힙

파이썬의 내장 모듈 heapq를 이용한다

 

import heapq

• heappush 이용한 원소 추가

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

 

• heappop을 이용한 원소 삭제

print(heapq.heappop(heap))

 

• 기존 리스트를 힙으로 변환

heapq.heapify(heap)

• 최대 힙 구현

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1

• K번째 최소값/최대값

import heapq

def kth_smallest(nums, k):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)

  kth_min = None
  for _ in range(k):
    kth_min = heapq.heappop(heap)
  return kth_min