공부
[알고리즘] - 힙 정렬(Heap Sort)
힙정렬이란? 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬방식 최댓값, 최솟값을 추출할 수 있는 자료구조 불안정 정렬 내림차순 정렬 => 최대 힙 / 오름차순 정렬 => 최소 힙 시간복잡도가 좋은편 가장 큰 값 몇개만 필요할 때 가장 효율적으로 사용 가능 완전 이진 트리란? [삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리] 힙 정렬 과정 최대 힙을 구성(내림차순 정렬 기준) 힙에서 한개씩 요소를 꺼내 배열 뒤에 저장 최대값부터 삭제하며 감소되는 순서로 정렬 시간 복잡도 최악 평균 최선 O(nlog₂n) O(nlog₂n) O(nlog₂n) [참고 자료] 링크
