[ Python ] Heap

Programmers 문제를 풀면서 계속 시간 초과가 나는 이슈가 발생했습니다. sort() 로 인한 시간 초과임을 짐작해보았고, 이를 heap으로 해결할 수 있음을 확인했습니다.

 

 

[ Heap ]

python 에서는 heap을 heapq라는 함수를 제공해주고 있습니다. heapq 모듈은 이진트리 기반의 최소 힙 자료구조를 제공합니다. 쉽게 설명하면 데이터를 추가하거나 삭제할 때, 가장 작은 값이 정렬되어 있는 자료구조입니다.

 

즉 데이터를 삽입하고 꺼낼 때, 전체를 다시 정렬해 줄 필요 없이 자료구조 알고리즘을 통해 결정됩니다.

heap 구조는 pop, push 의 시간 복잡도가 굉장히 적습니다.
heapq를 사용하지 않으면, sort() 를 사용해야 하고 이는 시간 초과를 발생시킬 수 있습니다.

 

import heapq

heap.heappush(list) # 가장 작은 값을 return & 삭제해준다
heapq.heappop(list, value) # 배열에 value를 삽입하고 자동으로 정렬해준다

 

01. heappush()

• 아래 코드를 살펴보면 5, 1, 9, 3을 순서대로 힙에 추가해 주었습니다.
• heap은 원소들이 항상 정렬된 상태로 추가됩니다.
• 따라서 결과는 정렬된 형태인 [1, 3, 9, 5]로 나오는 것을 확인할 수 있습니다.
• 해당 함수는 O(logN)의 시간 복잡도를 가집니다.

 

heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 9)
heapq.heappush(heap, 3)
print(heap) 

'''
[1, 3, 9, 5]
'''

 

02. heappop()

• 힙에서 원소를 삭제할 수 있습니다.
• 리스트를 인자로 넘겨주면, 가장 작은 원소를 삭제하고 삭제한 값을 return 해줍니다.
• 삭제할 때 index가 아닌 heap을 넘겨주는것을 꼭 꼭 기억해줍니다.

 

# heap = [1, 3, 9, 5]
print(heapq.heappop(heap))
print(heap)

'''
1
[3, 9, 5 ]
'''

 

03. heapify()

• 리스트를 -> 힙으로 만들어주는 함수입니다.
• O(N)의 시간 복잡도를 가집니다.

 

heap = [5, 2, 1, 4, 3]
heapq.heapify(heap)
print(heap)

'''
[1, 3, 5, 2, 4]
'''

 

 

👀 주의사항

그렇다면 heap[1]이 heap에서 두 번째로 작은 값이라고 생각해도 될까요 ???

 

🙅🏻‍♀️🙅🏻‍♀️🙅🏻‍♀️ 삐삐 절대 절대 절대

 

index로 원소를 접근할 때 heap[0] 이 가장 최솟값을 의미하는 것은 맞습니다.

가장 최솟값은 확실하지만 그 이후 값들도 정렬되었다고 볼 수 없습니다.

 

즉 두 번째로 작은 값을 구하기 위해서는 가장 작은 원소를 삭제한 뒤 heap[0] 을 통해 두 번째 최솟값에 접근해야 합니다.

 

 

응용을 하여 최대 힙으로 활용하는 방법은 이후에 작성하겠습니다.