CS/자료구조
[자료구조/Python] 힙(Heap) 개념과 Python에서의 사용
힙(Heap)이란?힙(Heap)이란 최댓값/최솟값을 빠르게 찾기 위해 고안되었으며, 루트 노드가 언제나 최댓값(최대 힙) 또는 최솟값(최소 힙)을 가지는 완전 이진트리(Complete Binary Tree)이다. 일반적인 리스트를 활용하여 최댓값/최솟값을 찾기 위한 max()/min() 함수의 시간 복잡도는 O(n)이다. 그러나 힙을 사용하면 O(log n)으로 수행이 가능하며, 정렬도 O(n log n)의 빠른 속도로 가능하다. 연산에 대한 자세한 이해보다는 힙에 대한 개념과 파이썬에서 활용할 수 있는 방법을 이해하는 것을 목표로 한다. 완전 이진 트리(Complete Binary Tree)마지막 레벨(Level)을 제외한 모든 레벨은 완전히 채워져 있는 이진트리이다. 삽입 연산을 수행할 경우 마지막 ..
