예니의 코딩일기

강의 "힙"은 최대 / 최소 원소를 빠르게 찾을 수 있는 알고리즘 입니다. 힙은 완전 이진 트리 자료구조를 통해 구현합니다. max heap min heap 연산 heapify : 힙 구성. O(N log N) insert : 삽입. O(log N) remove : 삭제. O(log N) import heapq heapq.heapify(L) heap.heappush(L, x) min = heapq.heappop(L) 응용 정렬 (heapsort) 우선 순위 큐 (priority queue) Step 5-3: 풀어서 내 것으로 만들자! 더 맵게 ⭐ heapq 라이브러리를 이용하여 푸는 문제! import heapq def solution(scoville, k): heapq.heapify(scoville) ..

강의 "힙"은 root node가 언제나 최대 또는 최소인 완전 이진 트리를 만족하는 자료구조 입니다. 모든 subtree는 최대 힙을 만족하지만 다른 subtree와의 관계는 정의되지 않습니다. 특정 키 값을 가지는 원소를 탐색하는 것에는 적절하지 않습니다. 노드의 추가/삭제는 마지막 노드에서만 가능합니다. 연산 __init__() : 비어있는 힙 생성 insert() : 원소 삽입 remove() : 최대 원소 반환 및 제거 배열을 이용한 이진 트리 표현 node = m left child node = 2m right child node = 2m + 1 parent node = m // 2 최대/최소 힙의 응용 우선순위 큐 (Priority Queue) : 시간 복잡도 O(log n) 힙 정렬 (he..