W wielu dyskusjach na temat sterty binarnej zwykle tylko klawisz zmniejszania jest wymieniony jako obsługiwana operacja dla sterty min. Na przykład rozdział 6.1 CLR i ta strona Wikipedii . Dlaczego zwykle nie jest wyświetlany klucz zwiększenia dla min-sterty? Wyobrażam sobie, że można to zrobić w O (wysokość), iteracyjnie zamieniając element podwyższony (x) z minimum jego elementów potomnych, dopóki żadne z jego elementów potomnych nie będzie większe niż x.
na przykład
IncreaseKey(int pos, int newValue)
{
heap[pos] = newValue;
while(left(pos) < heap.Length)
{
int smallest = left(pos);
if(heap[right(pos)] < heap[left(pos)])
smallest = right(pos);
if(heap[pos] < heap[smallest])
{
swap(smallest, pos);
pos= smallest;
}
else return;
}
}
Czy powyższe jest prawidłowe? Jeśli nie to dlaczego? Jeśli tak, dlaczego nie podano klucza zwiększenia dla min-sterty?
algorithms
data-structures
heaps
priority-queues
GatotPujo
źródło
źródło
Odpowiedzi:
Algorytm, który sugerujesz, jest po prostu heapify. I rzeczywiście - jeśli zwiększysz wartość elementu w min-stercie, a następnie skumulujesz jego poddrzewo, skończy się to legalną minaparą.
źródło
Przyczyną tego, że twojej operacji nie ma na liście, jest to, że nie interesują ją po prostu wszystkie operacje, które można łatwo wdrożyć przy użyciu określonej struktury danych, ale raczej w drugą stronę. Biorąc pod uwagę zestaw operacji, jaki jest najbardziej efektywny sposób (pod względem przestrzeni i czasu) na wdrożenie tych operacji. (Ale dodam do tego więcej później)
Stosy binarne implementują kolejkę priorytetową abstrakcyjnej struktury danych, która prosi o operacje to: pusty, dodaj_element (klucz o priorytecie), znajdź_min i usuń_min. Bardziej zaawansowane kolejki pozwalają również zmniejszyć priorytet klucza (w min_heap), a nawet go zwiększyć. W rzeczywistości dałeś implementację.
Dwie uwagi. Twoja operacja jest używana w funkcji heapify, która skutecznie konstruuje stertę z tablicy. W heapify twoja operacja jest powtarzana (zaczynając od ostatniego klucza).
A co najważniejsze, kod wykorzystuje pozycję węzła. Dla oszukującej kolejki priorytetowej czystej struktury danych. Ta struktura danych prosi o wykonanie określonej operacji z danym kluczem. Aby więc zmniejszyć lub zwiększyć priorytet elementu, najpierw musisz go zlokalizować. Myślę, że to główny powód, dla którego nie ma go na liście.
źródło
Myślę, że pierwszą rzeczą do rozważenia jest obsługiwana operacja?
Czy „wstawienie wartości z określonym, stałym kluczem” (np. Dla kluczy pobranych z dziedziny liczb całkowitych, wstawienie z kluczem = 3) odpowiada obsługiwanej operacji dla stosu min?
Nie, ponieważ operację tę można w prosty sposób zaimplementować za pomocą bardziej ogólnych obsługiwanych operacji. Podobnie wstawianie 2 elementów jednocześnie można wykonać za pomocą istniejącej
insertoperacji.Z drugiej strony
insertoperacji nie można zdefiniować inaczej niż poprzez ujawnienie szczegółów implementacji. Podobnie jest z operacjami wymienionymi na stronie wikipedii, zheapifywyjątkiem, które prawdopodobnie mogłyby być zaimplementowane przez sekwencjęinsert.Innymi słowy, istnieją podstawowe operacje na typie, które są ściśle związane ze szczegółami implementacji, aby mogły dobrze działać, i są inne operacje, które nie przestrzegają tej reguły, a zatem mogą być realizowane jako kombinacje kanonicznych.
Mając na uwadze tę definicję, czy sądzisz, że klawisz zwiększenia można wdrożyć wyłącznie z innymi obsługiwanymi operacjami, bez utraty wydajności? Jeśli tak, to nie jest to obsługiwana operacja według powyższej definicji, w przeciwnym razie możesz mieć rację.
O ile mi wiadomo, definicja obsługiwanej przeze mnie operacji jest moja. Nie jest to formalne i dlatego podlega dyskusji (choć wydaje mi się dość jasne). Byłbym jednak zadowolony, gdyby ktoś mógł dostarczyć źródło, które jasno i jednoznacznie definiuje, czym jest obsługiwana operacja dla typów danych, lub przynajmniej definiuje ją lepiej niż moje (czy ta definicja jest podana w CLR? Nie mam kopii ).
Moja druga uwaga dotyczy sposobu definiowania kolejki priorytetowej (która jest racją bytu składów binarnych). Czy
increase_keyoperacja jest niezbędna dla tego typu danych, tj. Do jego właściwego wykorzystania?Jak widać, mój kąt dotyczy definicji. Naprawdę nie udzielam odpowiedzi na twoje pytania, a jedynie niektóre wskazówki, więc ulepszenia są mile widziane.
źródło