c-code/heapifySort.c at main · dorondollev/c-code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>

#define MAXITEM 1000001
#define MAXLINE 256

char line[MAXLINE];
int count, a[MAXITEM];

main(){
	int i;
	count = 1;
	int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
	/*while(fgets(line, MAXLINE, stdin)!='\0'){
		sscanf(line,"%d\n",&a[count]);
		count++;
	}*/
/*	printarray(); */
	count=11;
	for(i=count-1;i>0;i--){
		heapify(i,count-1);
	}
/*	printarray(); */
	for(i=count-1;i>1;i--){
		int temp;
		temp = a[1];
		a[1] = a[i];
		a[i] = temp;
		heapify(1,i-1);
/*		printarray(); */
	}
	for(i=1;i<count;i++){
		printf("%d ",a[i]);
	}

}
/*
void heapify(int *A, int i)
{
        int largest;
        int l = left(i);
        int r = right(i);
        if (l <= heapSize && A[l]>A[i])
                largest = l;
        else
                largest = i;
        if (r <= length(A)&& A[r] > A[largest])
                largest = r;
        if(largest != i)
        {
                swap(&A[i], &A[largest]);
                heapify(A, largest);
        }
}
*/
heapify(p,q)
int p,q;
{
	if(p<=q/2){ /* a[i] is not a leaf */
		int temp,c;
		if(2*p+1>q){
			c = 2*p;
		}else if(a[2*p] > a[2*p+1]){
			c = 2*p;
		}else{
			c = 2*p+1;
		}
		if(a[p] < a[c]){
			temp = a[c];
			a[c] = a[p];
			a[p] = temp;
		}
		heapify(c,q);
	}
}

printarray()
{
	int i;
	for(i=1;i<count;i++){
		printf("%3d ",a[i]);
	}
	printf("\n");
}