64 lines
1.1 KiB
C
64 lines
1.1 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
void Heapify(int A[], int i, int heapsize) {
|
|
int left = 2 * i;
|
|
int right = 2 * i + 1;
|
|
int largest = i;
|
|
|
|
if (left < heapsize && A[left] > A[largest]) {
|
|
largest = left;
|
|
}
|
|
|
|
if (right < heapsize && A[right] > A[largest]) {
|
|
largest = right;
|
|
}
|
|
|
|
if (largest != i) {
|
|
int temp = A[largest];
|
|
A[largest] = A[i];
|
|
A[i] = temp;
|
|
Heapify(A, largest, heapsize);
|
|
}
|
|
}
|
|
|
|
void BuildHeap(int A[], int size) {
|
|
for (int i = size / 2 - 1; i >= 0; i--) {
|
|
Heapify(A, i, size);
|
|
}
|
|
}
|
|
|
|
void HeapSort(int A[], int size) {
|
|
BuildHeap(A, size);
|
|
for (int i = size - 1; i > 0; i--) {
|
|
int temp = A[0];
|
|
A[0] = A[i];
|
|
A[i] = temp;
|
|
Heapify(A, 0, i);
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
int size;
|
|
int res = scanf("%d", &size);
|
|
if (res != 1) {
|
|
fprintf(stderr, "Error reading size\n");
|
|
return 1;
|
|
}
|
|
|
|
int *array = malloc(sizeof(int) * size);
|
|
for (int i = 0; i < size; i++) {
|
|
res = scanf("%d", &array[i]);
|
|
if (res != 1) {
|
|
fprintf(stderr, "Error reading array element\n");
|
|
free(array);
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
HeapSort(array, size);
|
|
|
|
free(array);
|
|
return 0;
|
|
}
|