Jak mogę dalej optymalizować tę strukturę danych?

Question

Byłem niedawno poproszony zbudować strukturę danych, który obsługuje cztery operacje, a mianowicie

1. przycisku: Dodaj element do DS.
2. Pop: Usuń ostatni pchnięty element.
3. Find_max: Znajdź maksymalny element spośród aktualnie przechowywanych elementów.
4. Pop_max: Usuń maksymalny element z DS.

Elementy są liczbami całkowitymi.

Oto rozwiązanie zasugerowałem:

1. Weź stos.
2. Przechowywać parę elementów w nim. Para powinna być (element, max_so_far), gdzie element jest elementem tego indeksu, a max_so_far jest jak dotąd najwyższym wartościowanym elementem.
3. Przytrzymując element w stosie, sprawdź wartość maksymalnego elementu stosu max_so_far. Jeśli bieżąca liczba jest większa niż ta, ustaw wartość bieżącej pary jako wartość bieżącego elementu, a następnie zapisz poprzednią wartość: max_so_far . Oznacza to, że pchanie będzie po prostu operacją O(1).
4. Dla pop po prostu wyskocz element ze stosu. Ponownie, ta operacja to O(1).
5. Dla Find_max, zwróć wartość max_so_far najwyższego elementu stosu. Ponownie, O(1).
6. Popping the max element wymaga przechodzenia przez stos i jawnego usuwania elementu max i odpychania elementów na nim, po przydzieleniu nowych wartości max_so_far. Byłoby to liniowe.

Zostałem poproszony o poprawę, ale nie mogłem.

Jeśli chodzi o złożoność czasową, całkowity czas można poprawić, jeśli wszystkie operacje przebiegają w O(logn), jak sądzę. Jak to zrobić, jest czymś, czego nie jestem w stanie uzyskać.

Answer 1

Jednym ze sposobów jest przechowywanie wskaźników do elementów na podwójnie połączonej liście, a także w strukturze danych max-heap (posortowane według wartości).

Każdy element będzie przechowywać jego pozycję na podwójnie połączonej liście, a także na maksymalnej sterty.

W tym przypadku wszystkie operacje będą wymagały czasu O (1) na liście podwójnie połączonej oraz czasu O (log (n)) w strukturze danych sterty.

Answer 2

Jednym ze sposobów, aby uzyskać O (log n) operacji -Czas jest mash up z dwóch struktur danych, w tym przypadku podwójnie połączonej listy i kolejki priorytetowej (kupa parowanie jest dobrym wyborem).Mamy strukturę węzła, taką jak

struct Node { 
    Node *previous, *next; // doubly linked list 
    Node **back, *child, *sibling; // pairing heap 
    int value; 
} list_head, *heap_root; 

Teraz, aby naciskać, wciskamy obie struktury. Aby find_max, zwracamy wartość katalogu głównego sterty parowania. Aby wyświetlić lub pop_max, wyskakujemy z odpowiedniej struktury danych, a następnie używamy wskaźników innych węzłów do usunięcia w innej strukturze danych.

Answer 3

Zwykle, gdy trzeba znaleźć elementy według jakości A (wartość), a także według jakości B (kolejność wstawiania), rozpoczyna się odszukiwanie struktury danych, która ma dwie struktury danych wewnątrz siebie, lub inaczej przeplatane.

Na przykład: dwie mapy kluczy, dla których kluczem jest jakość A i jakość B, wartości których są współdzielonymi wskaźnikami do struktury, która zawiera iteratory z powrotem na obie mapy i wartością. Następnie masz log (n), aby znaleźć element za pomocą dowolnej jakości, a wymazanie to ~ O (logn), aby usunąć dwa iteratory z dowolnej mapy.

struct hybrid { 
    struct value { 
     std::map<std::string, std::shared_ptr<value>>::iterator name_iter; 
     std::map<int, std::shared_ptr<value>>::iterator height_iter; 
     mountain value; 
    }; 
    std::map<std::string, std::shared_ptr<value>> name_map; 
    std::map<int, std::shared_ptr<value>> height_map; 

    mountain& find_by_name(std::string s) {return name_map[s]->value;} 
    mountain& find_by_height(int height h) {return height_map[s]->value;} 
    void erase_by_name(std::string s) { 
     value& v = name_map[s]; 
     name_map.erase(v.name_iter); 
     height_iter.erase(v.height_iter); //note that this invalidates the reference v 
    } 
}; 

Jednak w twoim przypadku można zrobić nawet lepiej niż to O (logn), ponieważ wystarczy tylko „najnowsza” i „następny najwyższy”. Aby szybko uzyskać "najwyższą jakość", potrzebujesz szybkiego sposobu na wykrycie następnego najwyższego, co oznacza, że ​​należy wstępnie obliczyć wartość przy wstawianiu. Aby znaleźć pozycję "wysokość" względem reszty, potrzebujesz jakiejś mapy. Aby szybko "popować najnowszym", potrzebujesz szybkiego sposobu na wykrycie następnej nowości, ale jest to trywialnie obliczone. Zalecam utworzenie mapy lub sterty węzłów, gdzie kluczem jest wartość znajdowania maksimum, a wartości są wskaźnikiem do następnej najnowszej wartości. To daje ci wstawkę O (logn), O (1) znajdź najnowszą, O (1) lub O (logn) znajdź maksymalną wartość (w zależności od implementacji) i usuń ~ O (logn) przez dowolny indeks.

Answer 4

jeden sposób, aby to zrobić: -

Tworzenie maks sterty z elementów. W ten sposób będziemy mogli uzyskać/usunąć max-element w operacjach O (1). Wraz z tym możemy zachować wskaźnik do ostatniego elementu pchanego. I o ile wiem, usuwanie w stertach można zbudować w O (log n).