Heap 1. 힙은 완전이진트리를 기본으로한 자료구조로, O(logN)의 시간복잡도를 가지고 있다. 2. 여러 개의 값 중 최대값, 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 우선순위 큐 구현 시에 사용한다. 3. 힙은 반정렬 상태(느슨한 정렬 상태)를 유지한다. 이를테면 최소힙일 때, 작은 값이 상위 레벨에 있고 큰 값이 하위 레벨에 있다는 정도. 4. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류 최대힙 부모노드의 키 값이 자식노드의 키값보다 항상 크거나 같 힙. 최대 힙에서는 루트 노드에 이는 값이 제일 크므로 최대값을 찾는데 소요되는 연산의 시간복잡도는 O(1)이다. 그리고 완전 이진 트리이기 때문에 배열을 사용하여 효율적으로 관리할..
코드 import heapq, sys input = sys.stdin.readline tc = int(input()) h = [] for _ in range(tc): k = int(input()) if k == 0 and not h: print(0) elif k == 0 and h: print(-heapq.heappop(h)) # 나올 때 - 붙여서 원래 수로 바꿔준다. elif k!=0: heapq.heappush(h,-k) # 넣어줄 때 -를 붙여 최소힙을 최대힙으로 바꿔줄 수 있다. 파이썬의 heapq모듈은 최소 힙을 지원한다. 최대 힙을 지원해주지는 않는데, - 를 붙여서 최소 힙을 최대 힙으로 바꿀 수 있다.
