힙정렬

힙정렬

힙정렬은 비교적 빠른 정렬 방식중 하나이다. 먼저 트리와 힙에 대해서 알아본뒤, 힙정렬을 어떻게 하는지 알아보고 마지막으로 시간복잡도에 대해서 설명하겠다. Tree 위의 슬라이드에 보이는 것들이 모두 Tree구조이다. 이진트리 자식이 최대 2개있는 트리를 이진트리라고 부른다. 이진트리의 종류는 대표적으로 Full, Complete, Perfect가 있다. Full 이진트리중에서 자식 노드가 아예 없거나 혹은 2개 가지고 있는것을 Full 이진트리라고 부른다. Complete 왼쪽부터 노드가 하나하나 채워져 있는 것을 Complete 이진 트리라고 부른다. Perfect 모든 레벨의 노드가 꽉꽉 채워져 있는것을 Perfect 이진트리라고 부른다 힙 힙(heap)은 원래 어떤 물건들이 막 쌓여져 있는 모습을...