heap sort (1) 썸네일형 리스트형 33. Heap Sort 힙(Heap)은 원소를 정해진 규칙에 따라 배치한 완전 이진 트리로, 크게 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구분할 수 있다. 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작은 힙을 의미하며, 최대 힙은 그 반대이다. 형제 노드 간에는 대소 관계가 정해지지 않는다. 힙에 원소를 삽입하거나 힙에서 원소를 삭제할 경우 먼저 힙의 구조를 맞춘 다음 원소들의 교환을 통해서 대소 관계를 맞게 한다. 힙의 원소의 수가 $n$일 때 삽입/삭제 연산 한 번의 시간복잡도는 $\Theta(\text{lg }n)$이다. 이 힙을 이용해서 원소들을 정렬하는 것이 힙 정렬(Heap Sort)이다. 원소를 하나씩 힙에 삽입한 다음 힙의 루트에 있는 값을 빼는 과정을 반복하면 원소를 정렬할 수 있다. .. 이전 1 다음
