힙큐1 [python] 힙(heap)과 힙큐(heapq)란? 힙(heap) 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조 완전 이진트리 힙 property A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다. 최소 힙 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 된다. 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 키 값의 대소 관계 부모/자식 노드 ⭕ 형제노드 ❌ 시간복잡도 O(log n) 최소힙(heapq 모듈을 사용하지 않고 구현) # 최소힙 # 힙 삽입 연산 def heap_push(item): heap.append(item) child = len(heap) -.. 2023. 8. 11. 이전 1 다음
