728x90 최소힙2 [Python] heapq 모듈 사용법 heap 2021.10.03 - [ALGORITHM/개념 정리] - [Algorithm] 힙 (Heap) python에서는 heapq 모듈을 사용하여 리스트를 최소 힙처럼 사용 가능 heapq를 사용하여 만든 최소 힙의 0번째 인덱스는 항상 최소 값 heap = [] [원소 추가] heappush() : 내부적으로 이진 트리에 원소 추가, O(logN) heapq.heappush(heap, 1) [원소 삭제] heappop() : 가장 작은 원소를 삭제한 후 삭제한 값 리턴, O(logN) heapq.heappop(heap) [기존 리스트 힙으로 변환] heapq.heapify(heap) 2022. 1. 11. [Algorithm] 힙 (Heap) 힙(heap) 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰/작은 노드를 찾기 위해서 만든 자료구조 힙의 키를 우선순위로 활용하여 우선순위 큐를 구현할 수 있음 최대 힙 (max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 > 자식 노드의 키 값} 루트 노드 : 키 값이 가장 큰 노드 최소 힙 (min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 < 자식 노드의 키 값} 루트 노드 : 키 값이 가장 작은 노드 삽입 연산 삭제 연산 힙에서는 루트 노드의 원소만을 삭제할 수 있음 루트 노드의 원소를 삭제하여 반환 힙의 종류에 따라 최대값 또는 최소값 구할 수 있음 2021. 10. 3. 이전 1 다음 728x90
