Cześć,
Rozwiązuję zadanie algorytmiczne z użyciem kopca binarnego. W książce, z której się uczę, autor w przypadku kopca binarnego zawsze jako pierwszy element w tablicy traktuje element o indeksie 1, a ten o indeksie 0 zostawia pusty (tym samym potrzebna jest tablica o 1 element większa). Ja chciałem indeksować od 0, tak jak zwykle się robi. Niestety moje rozwiązanie z indeksowaniem od 0 nie działa, a to z indeksowaniem od 1 działa, czego nie rozumiem. Proszę o wyjaśnienie, co robię źle. Obie implementacje kopca poniźej (zamieszczam też sam program, może sposób w jaki korzystam z kopca powoduje problem):
Kopiec indeksowany od 0:
https://4programmers.net/Pastebin/15051
Kopiec indeksowany od 1:
https://4programmers.net/Pastebin/15053
Dodam, że implementacja błędna przechodzi połowę testów z zadania i wywala się dopiero na tych z większą ilością danych.
Do kopca wstawiam liczby ujemne, żeby pierwszym elementem kopca było minimum.
Zadania nie ma w internecie więc nie wstawiam linku do treści, mam nadzieję że to nie przeszkodzi.
- Rejestracja:ponad 5 lat
- Ostatnio:ponad rok
- Postów:36
0
edytowany 1x, ostatnio: licealista
- Rejestracja:prawie 7 lat
- Ostatnio:około 2 miesiące
- Postów:4
0
Zakładam, że rozumiesz na czym polegają kopce binarne i dlaczego można je łatwo przechowywać w tablicy. Oczywiście chodzi o łatwe policzenie indeksu rodzica mając indeks dziecka lub policzenie indeksu dziecka mając indeks rodzica. Zastanów się, czy w obu wersjach te obliczenia powinny być takie same (u Ciebie w kodzie są).
Wydaje mi się, że nie są. Funkcję heap_restore(...) specjalnie wywołuję tak jakbym indeksowal od 1 a potem odejmuję tę jedynkę, żeby nie było sytuacji w której mnożę 0 przez 2 żeby dostać indeks lewego syna, a dostaję dalej 0.

- Rejestracja:ponad 11 lat
- Ostatnio:7 dni
- Postów:1027
0
Ja chciałem indeksować od 0, tak jak zwykle się robi.
-> otóż nie w kopcu
Jeśli taka jest rzeczywiście konwencja, to w takim razie powinienem się dostosować. Po prostu mnie boli marnowanie tych dodatkowych bitów na miejsce w tablicy, które nie jest nigdy wykorzystywane :D Tak czy inaczej, ciekawi mnie co tam jest nie tak.

Nie tak jest przeliczanie indeksów. Jak chcesz mieć poprawnie, to np. lewy syn to będzie
(x+1)*2 - 1
, prawy syn to (x+1)*2 - 1 + 1
, ojciec to (x+1)/2 - 1
(w każdym z tych przypadków najpierw przeliczam na indeksowane od 1, potem wykonuję operację, potem przeliczam z powrotem). Uprość sobie te wzory jeśli chcesz. @licealista