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.
0
0
Masz kopię CLRS? Tam jest ładnie opisany heap od 1, ale może da się łatwo przerobić?
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ą).
0
Ja chciałem indeksować od 0, tak jak zwykle się robi. -> otóż nie w kopcu