#include<stdio.h>
//получить индекс левого потомка
int left(int i){
return i * 2 + 1;
}
//получить индекс правого потомка
int right(int i){
return i * 2 + 2;
}
//поменять местами два элемента массива
int swap(int *a,int i,int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
//вывести на экран массив
void print(int *a,int size){
int i;
for(i=0;i<size;i++){
printf("%d ",a[i]);
}
printf("\n");
}
//переупорядочивание поддерева
void heapify(int *a,int size,int i){
int l = left(i);
int r = right(i);
int largest = i;
if(l < size && a[i] < a[l]){
largest = l;
}
if(r < size && a[largest] < a[r]){
largest = r;
}
if(i != largest){
swap(a,i,largest);
heapify(a,size,largest);
}
}
//постройка кучи
void buildHeap(int *a,int size){
int i;
for(i=size/2 - 1;i>=0;i--){
heapify(a,size,i);
}
}
//сортировка кучей
void heapSort(int *a,int size){
buildHeap(a,size);
// printf("build\n");
// print(a,size);
while(--size > 0){
swap(a,0,size);
heapify(a,size,0);
}
}
int main(){
const int N = 9;
int arr[9] = {1,6,3,5,9,4,2,8,7};
print(arr,N);//вывести на экран исходный массив
heapSort(arr,N);//сортировка кучей
printf("=============\n");
print(arr,N);//вывод отсортированного массива
return 0;
} |