50 lines
1.1 KiB
C
50 lines
1.1 KiB
C
|
#include <stdio.h>
|
||
|
|
|
||
|
|
void swap(int* data, unsigned int i, unsigned int j) {
|
||
|
|
int tmp = data[i];
|
||
|
|
data[i] = data[j];
|
||
|
|
data[j] = tmp;
|
||
|
|
}
|
||
|
|
|
||
|
|
void siftdown(int* data, unsigned int n, unsigned int i) {
|
||
|
|
unsigned int left, right, ip;
|
||
|
|
while( i < n ) {
|
||
|
|
left = 2 * i + 1;
|
||
|
|
right = 2 * i + 2;
|
||
|
|
if( !(left < n) ) break;
|
||
|
|
|
||
|
|
ip = left;
|
||
|
|
|
||
|
|
if( right < n && data[ip] < data[right] ) ip = right;
|
||
|
|
if( data[ip] < data[i] ) break;
|
||
|
|
|
||
|
|
swap(data,i,ip);
|
||
|
|
i = ip;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void heapcreate(int* data, unsigned int n) {
|
||
|
|
for(unsigned int i = n/2; i > 0; i--) {
|
||
|
|
siftdown(data, n, i);
|
||
|
|
}
|
||
|
|
siftdown(data, n, 0);
|
||
|
|
}
|
||
|
|
|
||
|
|
void heapsort(int* data, unsigned int n) {
|
||
|
|
heapcreate(data, n);
|
||
|
|
for(unsigned int heapsize = n-1; heapsize > 0; heapsize--) {
|
||
|
|
swap(data,0,heapsize);
|
||
|
|
siftdown(data,heapsize,0);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
int main( int argc, char *argv[] ) {
|
||
|
|
int data[10] = { 3,7,5,1,2,8,9,0,4,6 };
|
||
|
|
heapsort(data, 10);
|
||
|
|
|
||
|
|
for(unsigned int i = 0; i < 10; i++) printf("%d ", data[i]);
|
||
|
|
printf("\n");
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|