JAVA heap sort
-
[JAVA/자료구조] 힙 정렬(Heap Sort)Language/Java 2021. 6. 13. 00:09
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 힙 정렬(Heap Sort) 최대 힙 트리나, 최소 힙 트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서 최대 힙을 구성하고, 오름차순 정렬을 위해서 최소힙을 구성한다. 이진 트리를 최대 힙으로 만들기 위해 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 시간 복잡도는 O(log n)이 걸린다. 힙 정렬(Heap Sort) 구현 n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼..