프로그래밍/알고리즘
2020. 4. 20.
Heap Sort (힙 정렬)
개념 - 힙 트리의 특징을 이용하여 정렬 (힙 트리에 원소들을 전부 삽입 후 힙의 루트에 있는 값을 이용하여 정렬) - 힙 트리는 완전이진트리구조를 가진 자료구조 - 추가적인 메모리를 전혀 필요로 하지 않음 - 항상 O(nLogn)정렬의 성능 - 선택정렬과 비슷 (매번 원소를 순환하면서 정렬하느냐 아니냐의 차이) * 힙트리는 첫번째 출처, 힙정렬은 두번째 출처에 알기쉽게 설명되어 있다. 원소 (16,14,10,8,7,9,3,2,4,1)를 정렬할 경우 (최대힙 기준) 힙트리에 삽입 1. 최상위 루트인 16을 추출 2. 추출되어 비어진 최상위 루트에 마지막 노드 1로 채움 3. 최대힙 특성에 맞춰 힙 트리를 재정렬 4. 재정렬 후 최상위 루트가 된 14를 추출 더이상 트리에 값이 남아있지 않을때까지 ..
