공부방

Heap이란?heap은 우선 순위 큐를 구현하는 자료구조로 이진 트리를 기반으로 구현된다. 부모 노드가 자식 노드보다 큰 경우 최대 힙, 부모 노드가 자식 노드보다 작은 경우 최소 힙이라고 한다. 힙의 삽입 및 삭제 연산은 O(logn)의 시간 복잡도로 이루어진다. 파이썬에 내부에서 사용 방식heapq 모듈을 이용하여 사용할 수 있다. 삽입 (heappush), 삭제 (heappop), 특정 배열을 힙 형태로 만들어주는 함수 (heapify) 지원heappop을 사용하면 배열 내의 가장 작은 값이 나오지만, 값이 삭제된다. 만약 삭제되길 원하지 않는다면 배열의 첫번째 원소에 접근하는 방식으로도 사용 가능하다. 기본적으로 최소힙만 지원하기 때문에 최대힙을 구현하기 위해서는 들어가는 값에 -를 곱해주어야 ..