heap
-
[자료구조] heapq moduleLanguage Study/Python 2021. 2. 2. 18:05
힙이란? 완전 이진 트리의 일종으로 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조이다. A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다. 라는 성질은 만족하며 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다. 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 모듈 설정 import heapq heapq의 경우 내장되어 있는 모듈이기 때문에 바로 import하여 사용할 수 있다. 힙 PUSH list를 heap처럼 사용할 수 있게 하는 것으로 빈 리스트에 인자를 넣는..