-
힙 정렬 (Heap Sort) 알고리즘Computer Science/자료구조&알고리즘 2021. 2. 17. 17:06
힙을 이용해서 리스트를 정렬하는 알고리즘
오름차순 정렬 기준으로, 최소 힙은 원소를 pop할 때
가장 작은 원소를 얻을 수 있다는 우선순위 큐 특성을 활용해 리스트를 정렬한다.
간단히 리스트의 모든 원소들을 힙에 push한 뒤,
다시 모든 원소들을 pop하여, pop한 순서대로 리스트에 대입하면 된다.
수도코드
heap_sort(int a[], int n){
heap h;
for(int i = 0; i < n; i++){
h.push(a[i]);
}
for(int i = 0; i < n; i++){
a[i] = h.pop();
}
}
시간 복잡도 : 힙의 삽입과 삭제는 모두 O(log n)의 시간 복잡도를 갖는다.
두 연산을 각각 n회 반복하므로 시간 복잡도는 총 O(n log n)이 된다.'Computer Science > 자료구조&알고리즘' 카테고리의 다른 글
크루스칼 알고리즘 (Kruskal Algorithm) with Union-Find 알고리즘 (0) 2021.02.26 퀵 정렬 (Quick Sort) 알고리즘 (0) 2021.02.17 합병 정렬 (Merge Sort) 알고리즘 (0) 2021.02.17 힙(heap)의 삽입과 삭제 (0) 2021.02.16 BFS (Breadth First Search) : 너비 우선 탐색 (0) 2021.02.15