Heap

Heap

Heap

완전 이진트리의 일종

여러개의 값들중 최대, 최소 값을 빠르게 찾을수 있음

반정렬 상태

부모노드의 값은 항상 자식노드보다 크다 => max heap

부모노드의 값이 항상 자식노드보다 작다 => min heap

형제노드간에는 대소관계 제약 없음

python heapq

min heap 으로 동작

삽입,삭제 시간복잡도 O(logN)

import heqpq q=[] # 삽입 heapq.heappush(q,1) # root 노드 꺼내기(가장 작은값) heapq.heappop(q) # heqp 구조로 만들기 heapq.heapify(q)

공유하기 글 요소 저작자표시

from http://akatapata.tistory.com/64 by ccl(A) rewrite - 2021-12-27 17:26:37