힙 정렬
-
힙(Heap)과 힙 정렬(Heap sort) - 자료구조, 알고리즘, 파이썬카테고리 없음 2019. 2. 15. 20:15
힙이라는 자료구조는 무엇일까. 한 노드(node)가 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 트리구조를 말한다.모든 노드의 값이 각자의 자식 노드의 값보다 크거나 같은 것을 최대 힙(Max heap)이라한다.모든 노드의 값이 각자의 자식 노드의 값보다 작거나 같은 것을 최소 힙(Min heap)이라한다.힙은 최대 힙이거나 최소 힙이어야 한다.또한, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 완전이진트리(complete binary tree)이다. 이러한 힙 속성(최대 힙, 완전이진트리)를 만족하면 다음 그림처럼 트리구조가 완성된다.힙은 완전이진트리 성질을 만족하기 때문에 1차원 배열로도 표현이 가능하다. [100, 19, 36, 17, 3, 25, 1, 2, 7]..