힙

❗️ 계속해서 업데이트 될 예정...

잘못된 부분이 있다면 알려주세요 🙏

힙

힙

힙의 특성을 만족하는 트리 기반의 자료구조.
최댓값과 최솟값을 찾아내는 연산을 빠르게 하기 위해 힙으로 구현하지만, 주의할 점은 힙은 정렬이 되어있지 않다.
파이썬에서는 heapq로 최소 힙만 구현되어 있다.
우선순위 큐나 다익스트라 알고리즘에 활용됨.

힙의 특성

• 최소 힙(Min Heap)
  부모 노드가 자식 노드의 값보다 항상 작은 힙.
• 최대 힙(Max Heap)
  부모 노드가 자식 노드의 값보다 항상 큰 힙.
  

힙 삽입

트리의 반만 탐색하기 때문에 시간 복잡도는 O(logn)이다. heapq.heappush()

힙 추출

루트만 추출하면 된다고 생각해 시간 복잡도가 O(1)로 생각할 수 있지만, 다시 힙의 특성을 유지하는 작업이 필요하므로 시간 복잡도는 O(logn)이다. heapq.heappop()

이진 힙 vs 이진 탐색 트리(BST)
힙은 상/하 관계를 보장, BST는 좌/우 관게를 보장한다.
모든 값이 정렬되어야 할 때는 BST를 사용하고,
가장 작은 값이나 가장 큰 값을 추출할 때는 이진 힙을 사용해야 한다.

힙 구현

파이썬에서는 heapq 모듈을 사용하여 힙을 구현한다.

import heapq
nums = [3,2,3,1,2,4,5,5,6]
heap = list()
for n in nums:
    heapq.heappush(heap, n)		# 값을 삽입한다
print(heap)				# [1, 2, 3, 3, 2, 4, 5, 5, 6]

print(heapq.heappop(heap))		# 최소 힙 즉, 최솟 값 : 1

print(heap)				# [2, 2, 3, 3, 6, 4, 5, 5]  다시 heap 특성을 유지함

heapify 를 이용하면 한번에 Push 한다.

import heapq
nums = [3,2,3,1,2,4,5,5,6]
heapq.heapify(nums)
print(nums)				# [1, 2, 3, 2, 3, 4, 5, 5, 6]

print(heapq.heappop(nums))		# 최소 힙 즉, 최솟 값 : 1

nlargest 와 nsmallest를 이용하면 n개의 가장 큰 값 또는 가장 작은 값을 추출할 수 있다.

import heapq
nums = [3,2,3,1,2,4,5,5,6]

print(heapq.nlargest(2, nums))		# [6, 5]
print(heapq.nlargest(2, nums)[-1])	# 2 번째로 가장 큰 값 : 5

print(heapq.nsmallest(2, nums))		# [1, 2]
print(heapq.nsmallest(2, nums)[-1])	# 2 번째로 가장 작은 값 : 2

파이썬에서 최대 힙
heapq는 최소 힙만 지원하는데 만약, 최대 힙을 구현하고 싶을 땐 어떻게 해야 할까?
방법은 간단하다.
값을 힙에 넣을 때 음수로 바꿔 넣은 뒤 최소 힙을 구현하면 최대 힙처럼 동작이 된다.

heap = list()
for n in arr:
    heapq.heappush(heap, -n) 
for _ in range(k):
    heapq.heappop(heap)
print( -heapq.heappop(heap) )