Muszę wykonać projekt: Kolejka priorytetowa reprezentowana w drzewie wyszukiwania binarnego. To jest dla mojej klasy algorytmów. "Nie jestem pewien, w jaki sposób chcesz użyć binarnego drzewa wyszukiwania jako kolejki priorytetowej. Wszystkie przykłady, które znalazłem w Internecie, dotyczyły stert i że "nigdy nie powinieneś zaimplementować kolejki priorytetowej w bst ale tylko w sterty". Czy ktoś mógłby mi wyjaśnić, co powinienem zrobić dokładnie? Dzięki!
Odpowiedzi:
0 dla odpowiedzi № 1Jako wskazówka kolejka priorytetowa musi być sprawnieobsługa wstawiania elementów, odczytywanie najmniejszej wartości (lub największej w kolejce o najwyższym priorytecie) i usuwanie najmniejszej wartości. BST obsługuje już szybkie wstawianie i usuwanie. Tak więc, gdybyś miał wszystkie elementy w kolejce priorytetowej przechowywane w BST, w jaki sposób znalazłbyś najmniejszą wartość? Sprawdź, czy możesz wykorzystać fakt, że BST przechowuje swoje elementy w porządku posortowanym, aby znaleźć bardzo szybki algorytm znajdowania najmniejszej wartości.