Czy jest stabilna kupa?

Czy istnieje struktura danych kolejki priorytetowej, która obsługuje następujące operacje?

• Wstaw (x, p) : dodaj nowy rekord x z priorytetem p
• StableExtractMin () : Zwraca i usuwa rekord z minimalnym priorytetem, zrywając powiązania według kolejności wstawiania .

Zatem po Insert (a, 1), Insert (b, 2), Insert (c, 1), Insert (d, 2), sekwencja StableExtractMin's zwróci a, następnie c, następnie b, a następnie d.

Oczywiście można użyć dowolnej struktury danych kolejki priorytetowej, przechowując parę jako rzeczywisty priorytet, ale interesują mnie struktury danych, które nie przechowują jawnie czasów wstawiania (ani kolejności wstawiania), analogicznie do stabilnego sortowania .$(p, time)$

Równoważnie (?): Czy istnieje stabilna wersja heapsortu, która nie wymaga dodatkowej przestrzeni?$\Omega(n)$

Metoda Bently-Saxe daje dość naturalną, stabilną kolejkę priorytetową.

Przechowuj swoje dane w sekwencji posortowanych tablic . A i ma rozmiar 2 i . Każda tablica utrzymuje również licznik C I . Wpisy tablicy A i [ c i ] , … , A i [ 2 i - 1 ] zawierają dane.$A_0,\ldots,A_k$$A_i$$2^i$$c_i$$A_i[c_i],\ldots,A_i[2^i-1]$

Dla każdego , wszystkie elementy A i dodaje się później, niż te, w A i + 1 , a w ramach poszczególnych A I elementy są uporządkowane według wartości opaskami jest podzielone przez umieszczenie starszych elementy przed nowymi elementami. Pamiętaj, że oznacza to, że możemy scalić A i i A i + 1 i zachować tę kolejność. (W przypadku powiązań podczas scalania, pobierz element z A i + 1. )$i$$A_i$$A_{i+1}$$A_i$$A_i$$A_{i+1}$$A_{i+1}$

Wstawić wartość , znaleźć najmniejsze i tak, że i zawiera 0 elementów, połączenie A 0 , ... , i - 1 i x przechowywać to w A ı i zestaw C 0 , ... , C, I, odpowiednio.$x$$i$$A_i$$A_0,\ldots,A_{i-1}$$x$$A_i$$c_0,\ldots,c_i$

Aby wyodrębnić min, znajdź największy indeks tak aby pierwszy element w A i [ c i ] był minimalny dla wszystkich i i inkrementował c i .$i$$A_i[c_i]$$i$$c_i$

Według standardowego argumentu daje to zamortyzowanego czasu na operację i jest stabilne z powodu kolejności opisanej powyżej.$O(\log n)$

Do sekwencji wstawień i wypakowań wykorzystuje n wpisów do tablicy (nie przechowuj pustych tablic) oraz O ( log n ) słów z danych księgowych. Nie odpowiada na wersję pytania Mihai, ale pokazuje, że stabilne ograniczenie nie wymaga dużego nakładu przestrzeni. W szczególności pokazuje, że nie ma dolnej granicy Ω ( n ) na potrzebnej dodatkowej przestrzeni.$n$$n$$O(\log n)$$\Omega(n)$

Aktualizacja: Rolf Fagerberg zwraca uwagę, że jeśli możemy przechowywać wartości zerowe (nie będące danymi), to całą strukturę danych można spakować do tablicy o rozmiarze , gdzie n to liczba wstawek do tej pory.$n$$n$

Po pierwsze należy zauważyć, że możemy zapakować do tablicy w tej kolejności (z A k najpierw, a następnie A k - 1 , jeżeli jest to niepusty, i tak dalej). Struktura tego jest całkowicie zakodowana przez binarną reprezentację n , liczbę wstawionych do tej pory elementów. Jeśli binarna reprezentacja n ma 1 w pozycji i , wtedy A i zajmie lokalizację tablicy 2 i , w przeciwnym razie nie zajmie żadnych lokalizacji tablicy.$A_k,\ldots,A_0$$A_k$$A_{k-1}$$n$$n$$i$$A_i$$2^i$

Podczas wstawiania, i długości naszej tablicy, zwiększ o 1, a my możemy scalić A 0 , … , A i plus nowy element przy użyciu istniejących stabilnych algorytmów scalania w miejscu.$n$$A_0,\ldots,A_i$

Teraz, gdy używamy wartości zerowych, polega na pozbyciu się liczników . W A i przechowujemy pierwszą wartość, następnie c i null wartości, a następnie pozostałe 2 i - c i - 1 . Podczas wyodrębniania-min możemy nadal znaleźć wartość do wyodrębnienia w czasie O ( log n ) , badając A 0 [ 0 ] , … , A k [ 0 ] . Kiedy znajdziemy tę wartość w A i [ $c_i$$A_i$$c_i$$2^i-c_i-1$$O(\log n)$$A_0[0],\ldots,A_k[0]$ ustawiamy A i [ 0 ] na null, a następnie przeprowadzamy wyszukiwanie binarne na A i, aby znaleźć pierwszą wartość inną niż null A i [ c i ] i zamienić A i [ 0 ] i A i [ c i ] .$A_i[0]$$A_i[0]$$A_i$$A_i[c_i]$$A_i[0]$$A_i[c_i]$

Rezultat końcowy: całą strukturę można zaimplementować za pomocą jednej tablicy, której długość jest zwiększana przy każdym wstawieniu, i jednego licznika, , który zlicza liczbę wstawień.$n$

Nie jestem pewien, jakie są twoje ograniczenia; czy następujące kwalifikują się? Przechowuj dane w tablicy, którą interpretujemy jako niejawne drzewo binarne (jak sterty binarne), ale z elementami danych na dolnym poziomie drzewa, a nie w jego wewnętrznych węzłach. Każdy wewnętrzny węzeł drzewa przechowuje mniejszą z wartości skopiowanych z jego dwóch elementów potomnych; w przypadku więzi skopiuj lewe dziecko.

Aby znaleźć minimum, spójrz na korzeń drzewa.

Aby usunąć element, zaznacz go jako usunięty (leniwe usunięcie) i propaguj w górę drzewa (każdy węzeł w ścieżce do katalogu głównego, który zawierał kopię usuniętego elementu, powinien zostać zastąpiony kopią drugiego elementu potomnego). Zachowaj liczbę usuniętych elementów i jeśli kiedykolwiek stanie się zbyt duża część wszystkich elementów, przebuduj strukturę zachowując kolejność elementów na najniższym poziomie - przebudowa zajmuje czas liniowy, więc ta część dodaje tylko stały amortyzowany czas do złożoność operacji.

Aby wstawić element, dodaj go do następnej wolnej pozycji w dolnym rzędzie drzewa i zaktualizuj ścieżkę do katalogu głównego. Lub, jeśli dolny wiersz się zapełni, dwukrotnie zwiększ rozmiar drzewa (ponownie z argumentem amortyzacji; zauważ, że ta część nie różni się niczym od potrzeby odbudowy, gdy standardowa binarna sterta przerośnie swoją tablicę).

Nie jest to jednak odpowiedź na bardziej rygorystyczną wersję pytania Mihai, ponieważ zużywa ona dwa razy więcej pamięci niż prawdziwa domniemana struktura danych, nawet jeśli leniwie zignorujemy koszt miejsca w przypadku usuwania.

Czy poprawna interpretacja twojego problemu jest następująca:

Musisz przechowywać N kluczy w tablicy A [1..N] bez informacji pomocniczych, takich, które możesz obsługiwać: * klawisz wstaw * usuń min, który wybiera najwcześniej wstawiony element, jeśli istnieje wiele minimów

Wydaje się to dość trudne, biorąc pod uwagę, że najbardziej niejawne struktury danych odgrywają trudność kodowania bitów w lokalnym uporządkowaniu niektórych elementów. Tutaj, jeśli wielu facetów jest równych, ich kolejność musi zostać zachowana, więc żadne takie sztuczki nie są możliwe.

Ciekawy.

Krótka odpowiedź: nie możesz.

Nieco dłuższa odpowiedź:

Będziesz potrzebował dodatkowej przestrzeni do przechowywania „wieku” swojego wpisu, co pozwoli ci rozróżnić identyczne priorytety. Będziesz potrzebował Ω ( n ) miejsca na informacje, które pozwolą na szybkie wstawianie i wyszukiwanie. Plus twoja ładowność (wartość i priorytet).$\Omega(n)$$\Omega(n)$

I dla każdego bloku danych przechowywanych, będziesz w stanie „ukryć” pewne informacje w adresie (np d d r ( X ) < d d r ( Y ) oznacza Y jest starsze niż X). Ale w tych „ukrytych” informacjach albo ukryjesz „wiek”, LUB „szybkie wyszukiwanie”. Nie oba.$addr(X) < addr(Y)$

Bardzo długa odpowiedź z niedokładną pseudo-matematyką:

Uwaga: jak wspomniano, sam koniec drugiej części jest szkicowy. Gdyby jakiś matematyk dostarczyłby lepszą wersję, byłbym wdzięczny.

Pomyślmy o ilości danych, które są zaangażowane na maszynie X-bitowej (powiedzmy 32 lub 64-bitowej), z szerokimi rekordami (wartość i priorytet) $P$

Masz zestaw potencjalnych rekordów, który jest częściowo uporządkowany: i ( a , 1 ) = ( a , 1 ), ale nie możesz porównać ( a , 1 ) i ( b , 1 ) .$(a,1) < (a,2)$$(a,1) = (a,1)$$(a,1)$$(b,1)$

Jednak chcesz być w stanie porównać dwie nieporównywalne wartości ze swojego zestawu rekordów, na podstawie tego, kiedy zostały wstawione. Więc masz tu inny zestaw wartości: tych, które zostały wstawione i chcesz zwiększyć jej częściowego porządku: wtw X został wstawiony przed Y .$X < Y$$X$$Y$

W najgorszym przypadku pamięć zostanie wypełniona zapisami formularza (z ? Innym dla każdego), więc będziesz musiał całkowicie polegać na czasie wstawiania, aby zdecydować, który z nich pójdzie pierwszy.$(?,1)$$?$

• $X - log_2(P)$$2^X$
• $P$

$X - log_2(P)$$O(n)$$n$

Ile bitów informacji zapewnia nam każda „komórka” pamięci?

• $W$$W$ being the machine word width).
• $X$ bits of address.

Now, let's assume $P \geq 1$ (payload is at least one machine word wide (usually one octet)). This means that $X - log_2(P) < X$, so we can fit the insertion order information in the cell's address. That's what happening in a stack : cells with the lowest address entered the stack first (and will get out last).

So, to store all our information, we have two possibilities :

• Store the insertion order in the address, and the payload in memory.
• Store both in memory and leave the address free for some other usage.

Obviously, in order to avoid waste, we'll use the first solution.

Now for the operations. I suppose you wish to have :

• $Insert(task, priority)$ with $O(log n)$ time complexity.
• $StableExtractMin()$ with $O(log n)$ time complexity.

Let's look at $StableExtractMin()$ :

The really really general algorithm goes like this :

1. Find the record with minimum priority and minimum "insertion time" in $O(log n)$.
2. Remove it from the structure in $O(log n)$.
3. Return it.

For example, in the case of a heap, it will be slightly differently organized, but the work is the same : 1. Find the min record in $0(1)$ 2. Remove it from the structure in $O(1)$ 3. Fix everything so that next time #1 and #2 are still $O(1)$ i.e. "repair the heap". This needs to be done in "O(log n)" 4. Return the element.

Going back to the general algorithm, we see that to find the record in $O(log n)$ time, we need a fast way to choose the right one between $2^(X - log_2(P))$ candidates (worst case, memory is full).

This means that we need to store $X - log_2(P)$ bits of information in order to retrieve that element (each bit bisects the candidate space, so we have $O(log n)$ bisections, meaning $O(log n)$ time complexity).

These bits of information might be stored as the address of the element (in the heap, the min is at a fixed address), or, with pointers for example (in a binary search tree (with pointers), you need to follow $O(log n)$ on average to get to the min).

Now, when deleting that element, we'll need to augment the next min record so it has the right amount of information to allow $O(log n)$ retrieval next time, that is, so it has $X - log_2(P)$ bits of information discriminating it from the other candidates.

That is, if it doesn't have already enough information, you'll need to add some. In a (non-balanced) binary search tree, the information is already there : You'll have to put a NULL pointer somewhere to delete the element, and without any further operation, the BST is searchable in $O(log n)$ time on average.

After this point, it's slightly sketchy, I'm not sure about how to formulate that. But I have the strong feeling that each of the remaining elements in your set will need to have $X - log_2(P)$ bits of information that will help find the next min and augment it with enough information so that it can be found in $O(log n)$ time next time.

The insertion algorithm usually just needs to update part of this information, I don't think it will cost more (memory-wise) to have it perform fast.

Now, that means that we'll need to store $X - log_2(P)$ more bits of information for each element. So, for each element, we have :

• The insertion time, $X - log_2(P)$ bits.
• The payload $P$ machine words.
• The "fast search" information, $X - log_2(P)$ bits.

Since we already use the memory contents to store the payload, and the address to store the insertion time, we don't have any room left to store the "fast search" information. So we'll have to allocate some extra space for each element, and so "waste" $\Omega(n)$ extra space.

If you implement your priority queue as a balanced binary tree (a popular choice), then you just have to make sure that when you add an element to the tree, it gets inserted to the left of any elements with equal priority.
This way, the insertion order is encoded in the structure of the tree itself.

I don't think that's possible

concrete case:

       x
    x    x
  x  x  1  x
1  x  

min heap with all x > 1

heapifying will eventually give something a choice like so

       x
    1    1
  x  x  x  x
x  x  

now which 1 to propagate to root?