#include <stdio.h>
#define XORSWAP(a, b) ((a)^=(b),(b)^=(a),(a)^=(b))
static int heap_size;
int parent(int i){
return i >> 1;
}
int left(int i){
return i << 1;
}
int right(int i){
return (i << 1) | 0x1;
}
void heapify(int *h, int i){
int l = left(i);
int r = right(i);
int largest;
if(l <= heap_size && h[l] > h[i])
largest = l;
else
largest = i;
if(r <= heap_size && h[r] > h[largest])
largest = r;
if(largest != i){
XORSWAP(h[i], h[largest]);
heapify(h, largest);
}
}
void make_heap(int *h, int len){
int i;
heap_size = len;
for(i = len/2; i >= 1; i--)
heapify(h, i);
}
int main(int argc, char *argv[]){
int i;
int h[11] = {0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
make_heap(h, 11);
for(i = 1; i < 11; i++)
printf((i
+ 1 == 11) ? "%d" : "%d ", h
[i
]);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIFhPUlNXQVAoYSwgYikgKChhKV49KGIpLChiKV49KGEpLChhKV49KGIpKQoKc3RhdGljIGludCBoZWFwX3NpemU7CgppbnQgcGFyZW50KGludCBpKXsKCXJldHVybiBpID4+IDE7Cn0KCmludCBsZWZ0KGludCBpKXsKCXJldHVybiBpIDw8IDE7Cn0KCmludCByaWdodChpbnQgaSl7CglyZXR1cm4gKGkgPDwgMSkgfCAweDE7Cn0KCnZvaWQgaGVhcGlmeShpbnQgKmgsIGludCBpKXsKCWludCBsID0gbGVmdChpKTsKCWludCByID0gcmlnaHQoaSk7CglpbnQgbGFyZ2VzdDsKCglpZihsIDw9IGhlYXBfc2l6ZSAmJiBoW2xdID4gaFtpXSkKCQlsYXJnZXN0ID0gbDsKCWVsc2UKCQlsYXJnZXN0ID0gaTsKCglpZihyIDw9IGhlYXBfc2l6ZSAmJiBoW3JdID4gaFtsYXJnZXN0XSkKCQlsYXJnZXN0ID0gcjsKCglpZihsYXJnZXN0ICE9IGkpewoJCVhPUlNXQVAoaFtpXSwgaFtsYXJnZXN0XSk7CgkJaGVhcGlmeShoLCBsYXJnZXN0KTsKCX0KfQoKdm9pZCBtYWtlX2hlYXAoaW50ICpoLCBpbnQgbGVuKXsKCWludCBpOwoJaGVhcF9zaXplID0gbGVuOwoKCWZvcihpID0gbGVuLzI7IGkgPj0gMTsgaS0tKQoJCWhlYXBpZnkoaCwgaSk7Cn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pewoJaW50IGk7CglpbnQgaFsxMV0gPSB7MCwgMSwgMywgNSwgNywgOSwgMiwgNCwgNiwgOCwgMTB9OwoKCW1ha2VfaGVhcChoLCAxMSk7Cglmb3IoaSA9IDE7IGkgPCAxMTsgaSsrKQogICAgICAgIHByaW50ZigoaSArIDEgPT0gMTEpID8gIiVkIiA6ICIlZCAiLCBoW2ldKTsKCglzY2FuZigiJWQiLCAmaSk7CglyZXR1cm4gMDsKfQo=