Heap

최대값이나 최솟값을 빠르게 찾아내기 위한 고안된 완전 이진트리를 기본으로 한 자료구조 이다.

최소 힙 : 자식 노드가 부모 노드보다 큰 완전 이진트리, 트리의 노드에는 가장 작은 값이 온다.

최대 힙 : 자식 노드가 부모 노드보다 작은 완전 이진트리, 트리의 노드에는 가장 큰 값이 온다.

Heap을 사용하면 좋은 점

가장 크거나 가장 작은 값을 찾아내기에 좋다. 이진트리 가장 위 root 노드에 가장 크거나 작은 값이 저장되어 있기 때문이다.

그리고 heap을 정렬할 때도 자신 부모노드와 자신을 비교하여,
최대 힙일 땐 자신이 더 크면 부모와 자리를 바꾸고
최소 힙일 땐 자신이 더 작으면 부모와 자리를 바꾸면 된다.

이렇다 보니 수 전체와 자신을 비교할 필요가 없어 시간 복잡도가 줄어든다.

시간복잡도

Heap 로직에 있어 가장 최악인 상황은 새로 추가된 노드가 Root 노드와까지 비교를 하게 되는 상황인데,
새로 들어오는 노드는 트리의 높이 만큼만 비교를 진행하면 된다.
그렇다면 알고리즘 수행에 필요한 단계수를 logN 만큼만 진행할 수 있으므로
Heap의 시간복잡도는 O(logN)이다.

파이썬에서 힙 사용하기

파이썬의 heapq는 모든 부모노드가 자식보다 작거나 같은 값을 갖는 이진트리이다.

import heapq

로 heapq 모듈을 import 한다.

• heapq.heapify(x)
  : list x를 heap 구조로 변환시켜 준다.
  

// heapfiy 직접 구현 해볼 것 -> 링크 첨부

🍒 maxHeap에서의 Heapfiy 구현

• heapq.heappush(heap, item)
  : heap이라는 이름의 힙에 item을 push한다.
  push된 item은 이진트리의 가장 마지막 노드에 위치하게 된다.

import heapq

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

heapq.heappush(heap, 10)

print(heap) #[3, 5, 1, 8, 4, 10] heapify로 정렬을 하지 않아 가장 작은 값이 위로오지 않았다.

• heapq.heapop(heap)
  : heap에서 가장 작은 항목을 pop한다.
  힙이 비어있으면 IndexError가 발생!

import heapq

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

heapq.heapify(heap) # [1, 4, 3, 8, 5]
heapq.heappush(heap, 10) # [1, 4, 3, 8, 5, 10]

print(heapq.heappop(heap)) # 1

print(heap) # [3, 4, 10, 8, 5] heappop 이후 가장 작은 값인 3이 힙의 root노드로 올라왔다.

• heapq.heappushpop(heap, item)
  : push랑 pop 섞어놓은 형태, item 푸시하고, heap에서 가장 작은 항목도 pop 해준다.
  

⭐아래 두 함수는 정렬 함수이다. 그러나 n값이 크면 sorted()로 정렬을 하는 것이 더 효율적이라고 한다. (python 공식 문서)⭐

• heapq.nlargest(n, iterable, key=None)
  : iterable에 정의된 데이터 집합에서 n개의 가장 큰 요소로 구성된 리스트를 반환 즉, 배열 내에서 가장 큰 순서대로 n개 반환해 준다는 의미이다.
  • iterable : member를 하나씩 차례로 반환 가능한 object
    예시로는 list, str, tuple이 있다.

import heapq

list = [3, 5, 16, 89, 4, -10, -99, 1]

print(heapq.nlargest(5, list)) # [89, 16, 5, 4, 3]

key를 활용하여 람다식으로 응용해 볼 수 있다.

import heapq

data = [

 {'goods': 'pizza', 'price':120},

 {'goods': 'chicken', 'price':380},
 
 {'goods': 'Tacco', 'price':987},
 
 {'goods': 'pudding', 'price':402},
]

smallest = heapq.nlargest(3, data, key=lambda god: god['price'])
print(smallest) 
# [{'goods': 'Tacco', 'price': 987}, {'goods': 'pudding', 'price': 402}, {'goods': 'chicken', 'price': 380}]

• heapq.nsmallest(n, iterable, key=None)
  : iterable에 정의된 데이터 집합에서 n개의 가장 작은 요소로 구성된 리스트를 반환 즉, 배열 내에서 가장 작은 순서대로 n개 반환해 준다는 의미이다.

최대 힙 만들기

import heapq

		nums = [3, 4, 5, 2]
		heap =[]
        max_heap = []

        for s in nums:
            heapq.heappush(heap, (-s, s))

        print(heap) # [(-5, 5), (-3, 3), (-4, 4), (-2, 2)]

        while heap:
            max_heap.append(heapq.heappop(heap)[1])
            
        print(max_heap) # [5, 4, 3, 2]

📃 references
1. https://docs.python.org/ko/3/library/heapq.html
2. https://www.programiz.com/dsa/heap-data-structure