최소 힙

우선순위 큐와 heap - python

참고 | 이코테2021 | 우선순위 큐 우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터꺼내서 확인해야 하는 경우 구현 방법 단순히 리스트 이용해 구현 가능 힙(heap)을 이용해 구현 가능 데이터가 N개일 때 구현 방식에 따른 시간복잡도 우선순위 큐 구현 방식 삽입 시간 삭제시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬) 이 경우 시간 복잡도는 O(NlogN) 힙의 특징 힙은 완전 이진 트리 자료구조의 일종 힙에서는 항상 루트 노드를 제거한다 최소 힙(m..