#include <stdio.h>
#include <time.h>
#include <sys/time.h>
#include <stdlib.h>
#define size 1000
void heap(void);
void heapSort(void);
void swap(int *, int *);
void viewTree(void);
void heapDown(int);
long getTime(void);
int array[size];
int m = size - 1;
main(){
for(int x = 0; x < size; x++){
array
[x
] = rand() % 100000; }
//viewTree();
heap();
//viewTree();
//printf("\n");
heapSort();
//viewTree();
long t = getTime();
}
void heap(){
//ヒープ
int i;
for(i = (m-1) / 2; i >= 0; i--){
heapDown(i);
}
}
void heapSort(){
//切り離し
while(m >= 1){
heap();
swap(&array[0], &array[m]);
//viewTree();
m--;
}
}
void swap(int *x, int *y){
//入れ替え
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
void viewTree(){
//木の表示
int i, j;
for(i = 1; i <= size; i *= 2){
for(j = 0; j < i; j++){
}
}
}
void heapDown(int j){
//ヒープ
if(2 * j + 2 <= m && array[j] < array[2*j+2] && array[2*j+1] < array[2*j+2]){
swap(&array[j], &array[2*j+2]);
heapDown(2*j+2);
}
else if(2 * j + 1 <= m && array[j] < array[2*j+1]){
swap(&array[j], &array[2*j+1]);
heapDown(2*j+1);
}
}
long getTime(){
struct timeval t;
gettimeofday(&t, NULL);
return time(NULL
) * 1000 + t.
tv_usec / 1000;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDx0aW1lLmg+CiNpbmNsdWRlIDxzeXMvdGltZS5oPgojaW5jbHVkZSA8c3RkbGliLmg+CgojZGVmaW5lIHNpemUgMTAwMAoKdm9pZCBoZWFwKHZvaWQpOwp2b2lkIGhlYXBTb3J0KHZvaWQpOwp2b2lkIHN3YXAoaW50ICosIGludCAqKTsKdm9pZCB2aWV3VHJlZSh2b2lkKTsKdm9pZCBoZWFwRG93bihpbnQpOwoKbG9uZyBnZXRUaW1lKHZvaWQpOwoKaW50IGFycmF5W3NpemVdOwoKaW50IG0gPSBzaXplIC0gMTsKCm1haW4oKXsKCQoJZm9yKGludCB4ID0gMDsgeCA8IHNpemU7IHgrKyl7CgkJYXJyYXlbeF0gPSByYW5kKCkgJSAxMDAwMDA7Cgl9CgkKCS8vdmlld1RyZWUoKTsKCQoJaGVhcCgpOwoJLy92aWV3VHJlZSgpOwoJCgkvL3ByaW50ZigiXG4iKTsKCQoJaGVhcFNvcnQoKTsKCS8vdmlld1RyZWUoKTsKCQoJbG9uZyB0ID0gZ2V0VGltZSgpOwoJCglwcmludGYoIiVsZFxuIiwgdCk7CgkKfQoKdm9pZCBoZWFwKCl7CgkvL+ODkuODvOODlwoJCglpbnQgaTsKCQoJZm9yKGkgPSAobS0xKSAvIDI7IGkgPj0gMDsgaS0tKXsKCQloZWFwRG93bihpKTsKCX0KCQp9Cgp2b2lkIGhlYXBTb3J0KCl7CgkvL+WIh+OCiumbouOBlwoJCgl3aGlsZShtID49IDEpewoJCQoJCWhlYXAoKTsKCQlzd2FwKCZhcnJheVswXSwgJmFycmF5W21dKTsKCQkvL3ZpZXdUcmVlKCk7CgkJbS0tOwoJCQoJfQoJCn0KCnZvaWQgc3dhcChpbnQgKngsIGludCAqeSl7CgkvL+WFpeOCjOabv+OBiAoJCglpbnQgdG1wOwoJCgl0bXAgPSAqeDsKCSp4ID0gKnk7CgkqeSA9IHRtcDsKCQp9Cgp2b2lkIHZpZXdUcmVlKCl7CgkvL+acqOOBruihqOekugoJCglpbnQgaSwgajsKCQoJZm9yKGkgPSAxOyBpIDw9IHNpemU7IGkgKj0gMil7CgkJCgkJZm9yKGogPSAwOyBqIDwgaTsgaisrKXsKCQkJcHJpbnRmKCIlZCIsIGFycmF5W2krai0xXSk7CgkJfQoJCQoJCXByaW50ZigiXG4iKTsKCQkKCX0KCQp9Cgp2b2lkIGhlYXBEb3duKGludCBqKXsKCS8v44OS44O844OXCgkKCWlmKDIgKiBqICsgMiA8PSBtICYmIGFycmF5W2pdIDwgYXJyYXlbMipqKzJdICYmIGFycmF5WzIqaisxXSA8IGFycmF5WzIqaisyXSl7CgkJc3dhcCgmYXJyYXlbal0sICZhcnJheVsyKmorMl0pOwoJCWhlYXBEb3duKDIqaisyKTsKCX0KCWVsc2UgaWYoMiAqIGogKyAxIDw9IG0gJiYgYXJyYXlbal0gPCBhcnJheVsyKmorMV0pewoJCXN3YXAoJmFycmF5W2pdLCAmYXJyYXlbMipqKzFdKTsKCQloZWFwRG93bigyKmorMSk7Cgl9CgkKfQoKbG9uZyBnZXRUaW1lKCl7CgkKCXN0cnVjdCB0aW1ldmFsIHQ7CgkKCWdldHRpbWVvZmRheSgmdCwgTlVMTCk7CgkKCWxvY2FsdGltZSgmdC50dl9zZWMpOwoJCglyZXR1cm4gdGltZShOVUxMKSAqIDEwMDAgKyB0LnR2X3VzZWMgLyAxMDAwOwoJCn0=