heap (1) 썸네일형 리스트형 자료구조 - 힙 (Heap) 힙은 부모가 항상 자식보다 작거나 같다 (최소힙)라는 특성을 만족하는 트리 기반의 자료구조입니다. 이번 포스트에서 다룰 힙은 최소힙이고 최소힙은 부모가 항상 자식보다 작기 때문에 트리의 루트가 가장 작은 값을 갖게 됩니다. 반대로 최대힙은 부모가 항상 자식보다 큰 트리가 되겠죠. 힙이라는 자료구조는 J.W.J. 윌리엄스가 1964년 힙 정렬 알고르짐을 고안하면서 파생된 부산물입니다. 보통 배열로 구현하며 다음 그림과 같이 부모와 자식 간의 상하 관계가 정의되어 있고 같은 레벨의 자식들끼리의 좌우 관계는 정의되어 있지 않습니다. 힙은 주로 배열로 구현되며, 위 그림 오른쪽처럼 배열로 표현할 수 있습니다. 루트 노드의 인덱스는 1부터 시작하고 그 다음 레벨 노드의 인덱스는 2,3, 그 다음 레벨 노드의 인덱.. 이전 1 다음
