Pamiętam, że stertę można użyć do wyszukiwania, czy element jest w niej, czy nie, przy złożoności czasu O (logN). Ale nagle nie mogę uzyskać szczegółów. Mogę tylko znaleźć getmin delete add i tak dalej.Wyszukaj element w stercie
Czy ktoś może podać podpowiedź?
Musisz przeszukać każdy element w stercie, aby określić, czy element jest w środku.
Jedna optymalizacja jest jednak możliwa (zakładamy tutaj maksymalną ilość sterty). Jeśli osiągnąłeś węzeł o mniejszej wartości niż szukany element, nie musisz szukać dalej od tego węzła. Jednak nawet przy tej optymalizacji szukanie nadal jest O (N) (trzeba średnio sprawdzić węzły N/2).
Myślę, że to, czego szukasz, to BST (drzewo wyszukiwania binarnego).
Niewłaściwe, jeśli masz już kolejkę priorytetową i chcesz sprawdzić, czy zawiera ona dany element. – finnw
Czy to w pełni prawda? Jako przykład należy posłużyć się poniższym stosem: '[5, 4, 1, 3]' Jeśli przeszukuję tę stertę (w formie tablicy) dla liczby 3, uderzę 1 i zgodnie z twoim algorytmem zatrzymam się tutaj stwierdzenie, że nie jest w kupie, kiedy tak naprawdę jest? Czy coś mi umyka? –
Po optymalizacji poddrzewo z rootem 1 nie będzie dalej przeszukiwane, ponieważ nie może zawierać 3. 3 znajduje się w innym poddrzewie. Zgadzam się, że wyszukiwanie liniowe (w przeciwieństwie do rekursywnego) może dać złą odpowiedź. –
@JamesSanders Jest to prawda we wszystkich przypadkach, nawet w przypadku wyszukiwania liniowego. Pełne drzewo binarne będzie miało wartość 3 jako lewe dziecko 4, a 1 będzie na tej samej wysokości co 4. Nawet jeśli wykonujesz wyszukiwanie liniowe, optymalizacja mówi, że 4> 3, a więc musisz, przynajmniej , porównaj dzieci w wieku 4 lat, oprócz wszystkich innych elementów na tej samej wysokości co 4. – lee