Monthly Archives: Ноябрь 2014

#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;
}