#include <iostream>
using namespace std;
#include <algorithm>
#include <iostream>
#define SIZE 20
const int d = 3;
//Всплытие
void siftup(int *a, int i){
int p = (i - 1) / d;
while((i != 0) && (a[p] > a[i])){
std::swap(a[i], a[p]);
i = p;
p = (i - 1) / d;
}
}
//n - длина массива
int min_child(int *a, int i, int n){
if(i*d + 1 >= n) return 0;
else{
int s = i*d + 1;
int min_key = a[s];
int last = (i + 1)*d;
if(last >= n) last = n - 1;
for(int j = s+1; j <= last; j++){
if(min_key > a[j]){
min_key = a[j];
s = j;
}
}
return s;
}
}
int min_child2(int *a, int i, int n){
int minchild = 0;
std::cout << "start minchild2" << std::endl;
if(i*d + 1 > n) return 0;
else{
int first_child = i*d + 1;
int last_child = std::min((1 + i)*d - 1, n);
int min_key = a[first_child];
std::cout << "else minchild2" << std::endl;
for(int i = first_child; i <= last_child; i++)
if(a[i] > min_key){
min_key = a[i];
minchild = i;
std::cout << "for loop minchild2" << std::endl;
}
std::cout << "return minchild2" << std::endl;
return minchild;
}
}
//Погружение
void siftdown(int *a, int i, int n){
std::cout << "siftdown called: i=" << i << std::endl;
int s = min_child(a, i, n);
std::cout << "min_child called: a[" << i << "]=" << a[i] << " result=" << s << std::endl;
while((s != 0) && (a[i] > a[s])){
std::cout << "swap i=" << i << " s=" << s << std::endl;
std::swap(a[i], a[s]);
i = s;
s = min_child(a, i, n);
std::cout << "min_child called: a[" << i << "]=" << a[i] << " result=" << s << std::endl;
}
}
//Преобразование массива в кучу
void build_dheap(int *a, int n){
for(int i = (n - 1)/*/d*/; i >= 0; i--)
siftdown(a, i, n);
std::cout << "after siftdown" << std::endl;
}
int main() {
int a[SIZE];
for(int i = 0; i < SIZE; i++){
a[i] = i % 10;
std::cout << a[i] << " ";
}
std::cout << std::endl;
build_dheap(a, SIZE);
std::cout << std::endl;
for(int i = 0; i < SIZE; i++)
std::cout << a[i] << " ";
return 0;
}
ICAgICNpbmNsdWRlIDxpb3N0cmVhbT4KICAgIHVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAgICAgCiAgICAjaW5jbHVkZSA8YWxnb3JpdGhtPgogICAgI2luY2x1ZGUgPGlvc3RyZWFtPgogICAgIAogICAgI2RlZmluZSBTSVpFIDIwCiAgICAgCiAgICBjb25zdCBpbnQgZCA9IDM7CiAgICAgCiAgICAvL9CS0YHQv9C70YvRgtC40LUKICAgIHZvaWQgc2lmdHVwKGludCAqYSwgaW50IGkpewogICAgCWludCBwID0gKGkgLSAxKSAvIGQ7CiAgICAJd2hpbGUoKGkgIT0gMCkgJiYgKGFbcF0gPiBhW2ldKSl7CiAgICAJCXN0ZDo6c3dhcChhW2ldLCBhW3BdKTsKICAgIAkJaSA9IHA7CiAgICAJCXAgPSAoaSAtIDEpIC8gZDsKICAgIAl9CiAgICB9CiAgICAgCiAgICAvL24gLSDQtNC70LjQvdCwINC80LDRgdGB0LjQstCwCiAgICBpbnQgbWluX2NoaWxkKGludCAqYSwgaW50IGksIGludCBuKXsKICAgIAlpZihpKmQgKyAxID49IG4pIHJldHVybiAwOwogICAgCWVsc2V7CiAgICAJCWludCBzID0gaSpkICsgMTsKICAgIAkJaW50IG1pbl9rZXkgPSBhW3NdOwogICAgCQlpbnQgbGFzdCA9IChpICsgMSkqZDsKICAgIAkJaWYobGFzdCA+PSBuKSBsYXN0ID0gbiAtIDE7CiAgICAJCWZvcihpbnQgaiA9IHMrMTsgaiA8PSBsYXN0OyBqKyspewogICAgCQkJaWYobWluX2tleSA+IGFbal0pewogICAgCQkJCW1pbl9rZXkgPSBhW2pdOwogICAgCQkJCXMgPSBqOwogICAgCQkJfQogICAgCQl9CiAgICAJCXJldHVybiBzOwogICAgCX0KICAgIH0KICAgICAKICAgIGludCBtaW5fY2hpbGQyKGludCAqYSwgaW50IGksIGludCBuKXsKICAgIAlpbnQgbWluY2hpbGQgPSAwOwogICAgCQogICAgCXN0ZDo6Y291dCA8PCAic3RhcnQgbWluY2hpbGQyIiA8PCBzdGQ6OmVuZGw7CiAgICAgCiAgICAJaWYoaSpkICsgMSA+IG4pIHJldHVybiAwOwogICAgCWVsc2V7CiAgICAJCWludCBmaXJzdF9jaGlsZCA9IGkqZCArIDE7CiAgICAJCWludCBsYXN0X2NoaWxkID0gc3RkOjptaW4oKDEgKyBpKSpkIC0gMSwgbik7CiAgICAJCWludCBtaW5fa2V5ID0gYVtmaXJzdF9jaGlsZF07CiAgICAJCQogICAgCQlzdGQ6OmNvdXQgPDwgImVsc2UgbWluY2hpbGQyIiA8PCBzdGQ6OmVuZGw7CiAgICAJCWZvcihpbnQgaSA9IGZpcnN0X2NoaWxkOyBpIDw9IGxhc3RfY2hpbGQ7IGkrKykKICAgIAkJCWlmKGFbaV0gPiBtaW5fa2V5KXsKICAgIAkJCQltaW5fa2V5ID0gYVtpXTsKICAgIAkJCQltaW5jaGlsZCA9IGk7CiAgICAJCQkJc3RkOjpjb3V0IDw8ICJmb3IgbG9vcCBtaW5jaGlsZDIiIDw8IHN0ZDo6ZW5kbDsKICAgIAkJCX0KICAgIAkJc3RkOjpjb3V0IDw8ICJyZXR1cm4gbWluY2hpbGQyIiA8PCBzdGQ6OmVuZGw7CiAgICAJCXJldHVybiBtaW5jaGlsZDsKICAgIAl9CiAgICB9CiAgICAgCiAgICAvL9Cf0L7Qs9GA0YPQttC10L3QuNC1CiAgICB2b2lkIHNpZnRkb3duKGludCAqYSwgaW50IGksIGludCBuKXsKICAgIAlzdGQ6OmNvdXQgPDwgInNpZnRkb3duIGNhbGxlZDogaT0iIDw8IGkgPDwgc3RkOjplbmRsOwogICAgCWludCBzID0gbWluX2NoaWxkKGEsIGksIG4pOwogICAgCXN0ZDo6Y291dCA8PCAibWluX2NoaWxkIGNhbGxlZDogYVsiIDw8IGkgPDwgIl09IiA8PCBhW2ldIDw8ICIgcmVzdWx0PSIgPDwgcyA8PCBzdGQ6OmVuZGw7CiAgICAJd2hpbGUoKHMgIT0gMCkgJiYgKGFbaV0gPiBhW3NdKSl7CiAgICAJCXN0ZDo6Y291dCA8PCAic3dhcCBpPSIgPDwgaSA8PCAiIHM9IiA8PCBzIDw8IHN0ZDo6ZW5kbDsKICAgIAkJc3RkOjpzd2FwKGFbaV0sIGFbc10pOwogICAgCQlpID0gczsKICAgIAkJcyA9IG1pbl9jaGlsZChhLCBpLCBuKTsKICAgICAgCSAgICBzdGQ6OmNvdXQgPDwgIm1pbl9jaGlsZCBjYWxsZWQ6IGFbIiA8PCBpIDw8ICJdPSIgPDwgYVtpXSA8PCAiIHJlc3VsdD0iIDw8IHMgPDwgc3RkOjplbmRsOwogICAgCX0KICAgIH0KICAgICAKICAgIC8v0J/RgNC10L7QsdGA0LDQt9C+0LLQsNC90LjQtSDQvNCw0YHRgdC40LLQsCDQsiDQutGD0YfRgwogICAgdm9pZCBidWlsZF9kaGVhcChpbnQgKmEsIGludCBuKXsKICAgIAlmb3IoaW50IGkgPSAobiAtIDEpLyovZCovOyBpID49IDA7IGktLSkKICAgIAkJc2lmdGRvd24oYSwgaSwgbik7CiAgICAJc3RkOjpjb3V0IDw8ICJhZnRlciBzaWZ0ZG93biIgPDwgc3RkOjplbmRsOwogICAgfQogICAgIAogICAgaW50IG1haW4oKSB7CiAgICAJaW50IGFbU0laRV07CiAgICAgCiAgICAJZm9yKGludCBpID0gMDsgaSA8IFNJWkU7IGkrKyl7CiAgICAJCWFbaV0gPSBpICUgMTA7CiAgICAJCXN0ZDo6Y291dCA8PCBhW2ldIDw8ICIgIjsKICAgIAl9CiAgICAJc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgICAKICAgIAlidWlsZF9kaGVhcChhLCBTSVpFKTsKICAgIAkKICAgIAlzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwogICAgCWZvcihpbnQgaSA9IDA7IGkgPCBTSVpFOyBpKyspCiAgICAJCXN0ZDo6Y291dCA8PCBhW2ldIDw8ICIgIjsKICAgIAkKICAgIAlyZXR1cm4gMDsKICAgIH0=