파이썬 개발
[Python] 힙 자료구조인 heapq에 대해 알아보자!
힙의 개념 힙은 완전 이진트리로 구성된 자료구조이다. 우선순위 큐를 위해 만들어진 자료구조이다. 힙 자료구조로 우선순위 큐를 구현할 때 삽입 삭제 모두 O(logN) 연산을 가진다. 최소 힙: 부모 노드의 값이 자식노드의 값보다 항상 작은 힙 최대 힙: 부모 노드의 값이 자식노드의 값보다 항상 큰 힙 위 사진과 같이 항상 완전 이진트리로 구성되어 최소 최대 값을 빠르게 찾아낼 수 있도록 설계되어있다. heapq 모듈 파이썬에선 heapq 모듈을 이용하여 최소 힙과 최대 힙 모두 구현할 수 있다. heapq 메서드 heappush(heap, item) 힙 불변성을 유지하면서 item 값을 heap으로 푸쉬한다. heapq.heappop(heap) 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 po..
