Hej, mam w tablicy 51837. Po zbudowaniu kopca maksymalnego (uporządkowanego) wychodzi mi
51837
57831
87531
W materiałach od prowadzącego mam:
87513
Na końcowy wynik sortowania nie ma to znaczenia, ale jest do dla mnie zastanawiające
Hej, mam w tablicy 51837. Po zbudowaniu kopca maksymalnego (uporządkowanego) wychodzi mi
51837
57831
87531
W materiałach od prowadzącego mam:
87513
Na końcowy wynik sortowania nie ma to znaczenia, ale jest do dla mnie zastanawiające
Heap sam w sobie nie jest posortowany i kolejność tych elementów, które wskazałeś nie ma znaczenia (zobacz jaki jest „warunek kopca”). Tablicę sortujemy poprzez algorytm heapsort, a to trochę więcej niż zbudowanie heapa.
Jest OK. Warunkiem kopca maksymalnego jest to, że dzieci są mniejsze od rodziców.
Pytanie jak budowałeś kopiec? Liniowo czy n log n? Może różnica wynika z zastosowanej metody tworzenia kopca.
Zobacz też:
https://www.geeksforgeeks.org/heap-sort/
Albo. lepiej, weź kopię CLRS:
https://www.amazon.pl/Introduction-Algorithms-Thomas-H-Cormen/dp/8120340078/ref=sr_1_2?__mk_pl_PL=%C3%85M%C3%85%C5%BD%C3%95%C3%91&crid=1KS589OH63XQF&keywords=clrs+algorithms&qid=1650909053&sprefix=clrs+algorithm%2Caps%2C280&sr=8-2