Struktura danych

0

Jakiej struktury danych użyć, tak by móc wykonywać następujące operacje :

  • znajdować element ekstremalny zgodnie z zadanym kluczem

  • modyfikować wartość dla określonego elementu

Z góry dziękuję za odpowiedź.

1

Nie do końca rozumiem pytanie, w jaki sposób określasz ekstremalność elementu?

Jeśli chcesz sortować po kluczu, to std::map będzie dobrym rozwiązaniem (ostatni/pierwszy element będzie ekstremalnym, można modyfikować wartość elementu). W przeciwnym wypadku prawdopodobnie zostaje Boost.MultiIndex.

1

Jeśli użyjesz drzewa binarnego to wyciągnięcie elementu ekstremalnego można zrobić w czasie O(1). Jego "modyfikacja" czyli de facto usunięcie i dodanie nowej wartości da sie wykonać w O(nlogn), bo zakładam że chcesz po takiej zmianie przywrócić poprawnej sortowanie.
Jak użyjesz posortowanej tablicy (;]) to wyciagać możesz w O(1) a zmodyfikować wartość i przywrócić posortowanie też w O(nlogn)/O(n) -> szukając połówkowo możesz znaleźć miejsce na ten zmodyfikowany element ale może istnieć potrzeba przesunięcia połowy tablicy ;]

1 użytkowników online, w tym zalogowanych: 0, gości: 1