힙 정렬은 힙 데이터 구조에서 수행됩니다. 우리는 힙이 완전한 이진 트리라는 것을 알고 있습니다. 힙 트리는 두 가지 유형이 있습니다. 최소 힙 또는 최대 힙. 최소 힙의 경우 루트 요소가 최소이고 최대 힙의 경우 루트가 최대입니다. 힙을 형성한 후 루트에서 요소를 삭제하고 마지막 요소를 루트로 보낼 수 있습니다. 이러한 스와핑 절차 후에 전체 어레이를 다시 힙해야 합니다. 루트에서 요소를 삭제하여 전체 배열을 정렬할 수 있습니다.
힙 정렬 기법의 복잡성
- 시간 복잡성: O(n 로그 n)
- 공간 복잡성: O(1)
입력 및 출력
Input: A list of unsorted data: 30 8 99 11 24 39 Output: Array before Sorting: 30 8 99 11 24 39 Array after Sorting: 8 11 24 30 39 99
알고리즘
무겁게 하다 (배열, 크기)
입력 - 데이터 배열 및 배열의 총 개수
출력 - 배열 요소를 사용한 최대 힙
Begin for i := 1 to size do node := i par := floor (node / 2) while par >= 1 do if array[par] < array[node] then swap array[par] with array[node] node := par par := floor (node / 2) done done End
heapSort(배열, 크기)
입력: 데이터 배열 및 배열의 총 개수
출력 -nbsp; 정렬된 배열
Begin for i := n to 1 decrease by 1 do heapify(array, i) swap array[1] with array[i] done End
예시
#include<iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 1; i<=size; i++)
cout << array[i] << " ";
cout << endl;
}
void heapify(int *array, int n) {
int i, par, l, r, node;
// create max heap
for(i = 1; i<= n; i++) {
node = i; par = (int)node/2;
while(par >= 1) {
//if new node bigger than parent, then swap
if(array[par] < array[node])
swap(array[par], array[node]);
node = par;
par = (int)node/2;//update parent to check
}
}
}
void heapSort(int *array, int n) {
int i;
for(i = n; i>= 1; i--) {
heapify(array, i);//heapify each time
swap(array[1], array[i]);//swap last element with first
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n+1]; //effective index starts from i = 1.
cout << "Enter elements:" << endl;
for(int i = 1; i<=n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
heapSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
} 출력
Enter the number of elements: 6 Enter elements: 30 8 99 11 24 39 Array before Sorting: 30 8 99 11 24 39 Array after Sorting: 8 11 24 30 39 99