히프 정렬 (1) 썸네일형 리스트형 [알고리즘] 히프 정렬 heap sort 히프 정렬 알고리즘 주요 특징 최대 히프(Max Heap) 구조의 특성을 최대한 활용 최대 히프 구조는 특정 조건을 만족하는 이진 트리 부모 노드의 값은 자식 노드보다 작지 않음 레벨 최소 결과적으로 루트 노드가 가장 큰 값을 가짐 최대 히프 구조를 계속 재구성하면서, 루트 노드를 한번에 하나씩 차례대로 추출하는 방식으로 정렬 복잡도분석 최대 히프 구조 초기 생성 : O(n log n) 최대 히프 재구성 : 매회 최대 O(log n), 총 n-1회 전체 비교 회수 : O(n log n) 장단점 수행 시간 아주 우수, O(n log n) 추가 기억공간 불필요 (cf) 2원 합병 정렬, 2n void Heap_Sorting(data A[], int n) { int i, j; data temp; // 최대 히.. 이전 1 다음
