[자료구조] 힙 | Heap

 

공유된 코드 - Color Scripter

 

힙, 힙트리는 부모 노드가 자식 노드보다 우선순위가 높은 값을 가지고있음이 보장되는 힙구조로 이루어진 트리형태의 자료구조입니다.

이 정의를 가지고 귀납적으로 생각해보면, 루트노드에 담겨있는 값이 항상 우선순위가 가장 높은 값임을 알 수 있습니다.

또, 균형 이진트리 형태를 항상 유지하므로, 값의 삭제 및 삽입을 항상 O(logN)시간복잡도 내에 할 수 있음이 보장됩니다.

 

이러한 힙트리의 특성을 활용해, 다익스트라(Dijkstra), 힙 정렬(Heap Sort)등을 수행할 수 있습니다.

 

위 링크는 힙트리를 개인적으로 구현한 소스코드입니다.