Jak zbudowanie sterty może być złożonością czasową O (n)?

Czy ktoś może wyjaśnić, w jaki sposób budowanie sterty może być złożonością O (n)?

Wstawianie elementu do sterty jest O(log n), a wstawianie jest powtarzane n / 2 razy (pozostałe są liśćmi i nie mogą naruszać właściwości sterty). To oznacza, że ​​złożoność powinna być O(n log n), jak sądzę.

Innymi słowy, dla każdego elementu, który „stertyzujemy”, może on wymagać odfiltrowania raz dla każdego poziomu stosu do tej pory (czyli poziomów log n).

czego mi brakuje?

Myślę, że w tym temacie jest kilka pytań:

• Jak wdrożyć, buildHeapaby działało w czasie O (n) ?
• Jak pokazać, że buildHeapdziała w czasie O (n), gdy jest poprawnie zaimplementowany?
• Dlaczego ta sama logika nie działa, aby sortowanie sterty działało w czasie O (n) zamiast O (n log n) ?

Jak wdrożyć, buildHeapaby działało w czasie O (n) ?

Często odpowiedzi na te pytania koncentrują się na różnicy między siftUpi siftDown. Właściwy wybór między siftUpi siftDownjest krytyczny dla uzyskania wydajności O (n)buildHeap , ale nie robi nic, aby pomóc zrozumieć różnicę pomiędzy buildHeapi heapSortogólnie. Rzeczywiście, odpowiednie implementacje obu buildHeapi heapSortbędą korzystać tylkosiftDown . Ta siftUpoperacja jest potrzebna tylko do wstawiania do istniejącej sterty, więc może być wykorzystana do zaimplementowania kolejki priorytetowej przy użyciu na przykład sterty binarnej.

Napisałem to, aby opisać, jak działa maksymalna sterty. Jest to typ sterty zwykle używany do sortowania sterty lub do kolejki priorytetowej, w której wyższe wartości wskazują wyższy priorytet. Przydatna jest również sterta min; na przykład podczas wyszukiwania elementów z kluczami całkowitymi w porządku rosnącym lub ciągami znaków w kolejności alfabetycznej. Zasady są dokładnie takie same; wystarczy zmienić kolejność sortowania.

Właściwość sterta określa, że ​​każdy węzeł w stercie binarnym musi być co najmniej tak duży, jak oba jego elementy potomne. W szczególności oznacza to, że największy element na stosie znajduje się w katalogu głównym. Przesiewanie w dół i przesiewanie w górę to w zasadzie ta sama operacja w przeciwnych kierunkach: przesuń naruszający węzeł, aż spełni właściwości sterty:

• siftDown zamienia zbyt mały węzeł z jego największym dzieckiem (przesuwając go w dół), aż będzie co najmniej tak duży, jak oba węzły pod nim.
• siftUp zamienia węzeł, który jest zbyt duży z rodzicem (tym samym przesuwając go w górę), aż nie będzie większy niż węzeł nad nim.

Liczba operacji wymaganych siftDowni siftUpjest proporcjonalna do odległości, jaką może pokonać węzeł. Ponieważ siftDownjest to odległość do dolnej części drzewa, więc siftDownjest kosztowna dla węzłów na szczycie drzewa. Dzięki siftUp, praca jest proporcjonalna do odległości do szczytu drzewa, więc siftUpjest kosztowna dla węzłów na dole drzewa. Chociaż obie operacje są w najgorszym przypadku O (log n) , w stercie tylko jeden węzeł znajduje się na górze, podczas gdy połowa węzłów leży na dolnej warstwie. Nie powinno więc dziwić, że gdybyśmy musieli zastosować operację do każdego węzła, wolelibyśmy siftDownwięcej siftUp.

buildHeapFunkcja przyjmuje tablicę nieposortowane przedmiotów i przenosi je do momentu spełnienia wszystkich właściwość stos, tworząc w ten sposób poprawny sterty. Istnieją dwa podejścia można by przyjąć za buildHeapwykorzystaniem siftUpi siftDownoperacje Opisaliśmy.

1. Rozpocznij na górze stosu (na początku tablicy) i wywołaj siftUpkażdy element. Na każdym etapie poprzednio przesiane elementy (elementy przed bieżącym elementem w tablicy) tworzą prawidłową stertę, a przesiewanie następnego elementu w górę umieszcza go w prawidłowej pozycji na stercie. Po przesianiu każdego węzła wszystkie elementy spełniają właściwość sterty.

2. Lub idź w przeciwnym kierunku: zacznij od końca tablicy i cofnij się do przodu. Przy każdej iteracji przesiewasz przedmiot w dół, aż znajdzie się we właściwej lokalizacji.

Które wdrożenie buildHeapjest bardziej wydajne?

Oba te rozwiązania wygenerują prawidłową stertę. Nic dziwnego, że bardziej wydajna jest druga operacja siftDown.

Niech h = log n reprezentuje wysokość stosu. Praca wymagana do tego siftDownpodejścia jest sumą

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

Każdy termin w sumie ma maksymalną odległość, którą musi przesunąć węzeł na danej wysokości (zero dla dolnej warstwy, h dla korzenia) pomnożony przez liczbę węzłów na tej wysokości. Natomiast suma za wywołanie siftUpw każdym węźle wynosi

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

Powinno być jasne, że druga suma jest większa. Sam pierwszy termin to hn / 2 = 1/2 n log n , więc to podejście ma w najlepszym razie złożoność O (n log n) .

Jak udowodnimy, że suma dla tego siftDownpodejścia jest rzeczywiście O (n) ?

Jedną z metod (istnieją inne analizy, które również działają) jest przekształcenie skończonej sumy w szereg nieskończony, a następnie użycie szeregu Taylora. Możemy zignorować pierwszy termin, który wynosi zero:

Jeśli nie masz pewności, dlaczego każdy z tych kroków działa, oto uzasadnienie tego procesu w słowach:

• Wszystkie warunki są dodatnie, więc suma skończona musi być mniejsza niż suma nieskończona.
• Szereg jest równy szeregowi mocy oszacowanemu przy x = 1/2 .
• Ta seria mocy jest równa (stałemu czasowi) pochodnej szeregu Taylora dla f (x) = 1 / (1-x) .
• x = 1/2 mieści się w przedziale zbieżności tej serii Taylora.
• Dlatego możemy zamienić szereg Taylora na 1 / (1-x) , różnicować i oceniać, aby znaleźć wartość szeregu nieskończonego.

Ponieważ suma nieskończona wynosi dokładnie n , dochodzimy do wniosku, że suma skończona nie jest większa, a zatem wynosi O (n) .

Dlaczego sortowanie sterty wymaga czasu O (n log n) ?

Jeśli możliwe jest uruchomienie buildHeapw czasie liniowym, dlaczego sortowanie sterty wymaga czasu O (n log n) ? Sortowanie sterty składa się z dwóch etapów. Najpierw wywołujemy buildHeaptablicę, która wymaga O (n) czasu, jeśli jest zaimplementowana optymalnie. Następnym etapem jest wielokrotne usuwanie największego elementu ze sterty i umieszczanie go na końcu tablicy. Ponieważ usuwamy element ze sterty, tuż za końcem sterty zawsze jest otwarte miejsce, w którym możemy przechowywać przedmiot. Tak więc sortowanie sterty osiąga uporządkowany porządek poprzez sukcesywne usuwanie następnego największego przedmiotu i umieszczanie go w tablicy, zaczynając od ostatniej pozycji i przesuwając się do przodu. To złożoność tej ostatniej części dominuje w rodzaju sterty. Pętla wygląda następująco:

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

Oczywiście, pętla działa O (n) razy ( n - 1, by być dokładnym, ostatni element jest już na miejscu). Złożoność deleteMaxstosu wynosi O (log n) . Zwykle jest to realizowane przez usunięcie korzenia (największego elementu pozostawionego na stercie) i zastąpienie go ostatnim elementem na stercie, który jest liściem, a zatem jednym z najmniejszych elementów. Ten nowy root prawie na pewno naruszy właściwość sterty, więc musisz zadzwonić, siftDowndopóki nie przeniesiesz go z powrotem do akceptowalnej pozycji. To również powoduje przeniesienie następnego największego przedmiotu do korzenia. Zauważ, że w przeciwieństwie do tego, buildHeapgdzie w przypadku większości węzłów wzywamy siftDownod dołu drzewa, teraz wzywamy siftDownod góry drzewa podczas każdej iteracji!Chociaż drzewo kurczy się, nie kurczy się wystarczająco szybko : wysokość drzewa pozostaje stała, dopóki nie usuniesz pierwszej połowy węzłów (po całkowitym usunięciu dolnej warstwy). Następnie przez następny kwartał wysokość wynosi h - 1 . Tak więc całkowita praca dla tego drugiego etapu wynosi

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

Zwróć uwagę na przełącznik: teraz zerowy przypadek roboczy odpowiada jednemu węzłowi, a przypadek roboczy h odpowiada połowie węzłów. Ta suma wynosi O (n log n), podobnie jak nieefektywna wersja buildHeaptego jest implementowana za pomocą siftUp. Ale w tym przypadku nie mamy wyboru, ponieważ próbujemy sortować i wymagamy następnego następnego największego elementu do usunięcia.

Podsumowując, praca dla sortowania sterty jest sumą dwóch etapów: O (n) czas na buildHeap i O (n log n) do usunięcia każdego węzła w kolejności , więc złożoność wynosi O (n log n) . Możesz udowodnić (korzystając z niektórych pomysłów z teorii informacji), że dla sortowania opartego na porównaniu O (n log n) jest najlepszym, na co możesz liczyć, więc nie ma powodu, aby być rozczarowanym tym lub oczekiwać, że sortowanie sterty pozwoli osiągnąć O (n) czas, który buildHeapspełnia.

Twoja analiza jest poprawna. Jednak nie jest ciasno.

Nie jest łatwo wyjaśnić, dlaczego budowanie sterty jest operacją liniową, lepiej ją przeczytaj.

Wielki analiza algorytmu można zobaczyć tutaj .

Główną ideą jest to, że w build_heapalgorytmie rzeczywisty heapifykoszt nie O(log n)dotyczy wszystkich elementów.

Po heapifywywołaniu czas działania zależy od tego, jak daleko element może się przesunąć w dół drzewa przed zakończeniem procesu. Innymi słowy, zależy to od wysokości elementu w stercie. W najgorszym przypadku element może spaść aż do poziomu liścia.

Policzmy pracę wykonaną poziom po poziomie.

Na najniższym poziomie są 2^(h)węzły, ale nie wzywamy heapifyżadnego z nich, więc praca wynosi 0. Na następnym poziomie są 2^(h − 1)węzły i każdy może przejść w dół o 1 poziom. Na 3. poziomie od dołu znajdują się 2^(h − 2)węzły, z których każdy może przejść w dół o 2 poziomy.

Jak widać, nie wszystkie operacje rozsypywania są O(log n), dlatego otrzymujesz O(n).

Intuicyjnie:

„Złożoność powinna wynosić O (nLog n) ... dla każdego elementu, który„ stertyzujemy ”, może potencjalnie wymagać odfiltrowania raz dla każdego poziomu stosu do tej pory (czyli poziomów log n).”

Nie do końca. Twoja logika nie tworzy ścisłej więzi - przesadza z oszacowaniem złożoności każdego heapify. W przypadku budowania od podstaw, wstawianie (heapify) może być znacznie mniejsze niż O(log(n)). Proces przebiega następująco:

(Krok 1) Pierwsze n/2elementy trafiają do dolnego rzędu stosu. h=0, więc heapify nie jest potrzebne.

(Krok 2) Następne elementy idą w rzędzie 1 w górę od dołu. , heapify filtry o 1 poziom w dół.n/22h=1

(Krok i ) Następne elementy idą w rzędzie w górę od dołu. obniża poziomy filtrów .n/2iih=ii

(Krok dziennika (n) ) Ostatni element idzie w rzędzie w górę od dołu. obniża poziomy filtrów .n/2log2(n) = 1log(n)h=log(n)log(n)

ZAUWAŻ: że po pierwszym kroku 1/2elementy (n/2)są już w stercie i nie musieliśmy nawet wywoływać jednorazowo wezwania. Zauważ też, że tylko jeden element, rdzeń, w rzeczywistości powoduje pełną log(n)złożoność.

Teoretycznie:

Całkowitą Nliczbę kroków do zbudowania sterty wielkości nmożna zapisać matematycznie.

Na wysokości ipokazaliśmy (powyżej), że będą elementy, które będą musiały wywołać heapify, i wiemy, że heapify na wysokości to . To daje:n/2i+1iO(i)

Rozwiązanie ostatniego sumowania można znaleźć, biorąc pochodną obu stron znanego równania szeregów geometrycznych:

Wreszcie podłączenie x = 1/2do powyższego równania daje wynik 2. Podłączenie tego do pierwszego równania daje:

Zatem łączna liczba kroków ma rozmiar O(n)

Byłoby O (n log n), jeśli zbudowałeś stertę przez wielokrotne wstawianie elementów. Możesz jednak wydajniej utworzyć nową stertę, wstawiając elementy w dowolnej kolejności, a następnie stosując algorytm do „stertyfikowania” ich we właściwej kolejności (w zależności od rodzaju sterty, oczywiście).

Zobacz http://en.wikipedia.org/wiki/Binary_heap „Budowanie sterty” dla przykładu. W tym przypadku zasadniczo pracujesz od najniższego poziomu drzewa, zamieniając węzły nadrzędne i potomne, dopóki warunki sterty nie zostaną spełnione.

Jest już kilka świetnych odpowiedzi, ale chciałbym dodać trochę wizualnego wyjaśnienia

Teraz spójrz na obrazek, są
n/2^1 zielone węzły o wysokości 0 (tutaj 23/2 = 12)
n/2^2 czerwone węzły o wysokości 1 (tutaj 23/4 = 6)
n/2^3 niebieski węzeł o wysokości 2 (tutaj 23/8 = 3)
n/2^4 fioletowe węzły o wysokości 3 (tutaj 23/16 = 2),
więc są n/2^(h+1)węzły dla wysokości h
Aby znaleźć złożoność czasu, policzmy ilość pracy wykonanej lub max liczbę iteracji wykonanych przez każdy węzeł,
teraz można zauważyć, że każdy węzeł może wykonaj (atmost) iteracje == wysokość węzła

Green  = n/2^1 * 0 (no iterations since no children)  
red    = n/2^2 * 1 (heapify will perform atmost one swap for each red node)  
blue   = n/2^3 * 2 (heapify will perform atmost two swaps for each blue node)  
purple = n/2^4 * 3 (heapify will perform atmost three swaps for each purple node)   

więc dla wszystkich węzłów o wysokości h maksymalna wykonana praca wynosi n / 2 ^ (h + 1) * h

Teraz wykonano całą pracę

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

teraz dla dowolnej wartości h , sekwencji

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

nigdy nie przekroczy 1
Tak więc złożoność czasowa nigdy nie przekroczy O (n) dla budowy stosu

Jak wiemy, wysokość stosu to log (n) , gdzie n to całkowita liczba elementów.    Niech to reprezentuje jako h.
Kiedy wykonujemy operację heapify, elementy na ostatnim poziomie ( h ) nie poruszą się nawet krok.
   Liczba elementów na drugim ostatnim poziomie ( h-1 ) wynosi 2 ^h-1 i mogą się one poruszać na maksymalnie 1 poziomie (podczas heapify).
   Podobnie dla ı ^{TH ,} poziom mamy 2 ⁱ elementów, które mogą się poruszać hi pozycji.

Dlatego łączna liczba ruchów = S = 2 ^h * 0 + 2 ^h-1 * 1 + 2 ^h-2 * 2 + ... 2 ⁰ * h

                                               S = 2 ^godz. {1/2 + 2/2 ² + 3/2 ³ + ... h / 2 ^godz. } ----------------------- -------------------------- 1
to jest seria AGP , aby rozwiązać ten podział, podziel obie strony przez 2
                                               S / 2 = 2 ^h {1/2 ² + 2/2 ³ + ... h / 2 ^{h + 1} } --------------------------------- ---------------- 2
odjęcie równania 2 od 1 daje
                                               S / 2 = 2 ^h { 1/2 + 1/2 ² + 1/2 ³ + ... + 1 / 2 ^godz. + Godz. / 2 ^{godz. + 1} }
                                                S = 2 ^{h + 1} { 1/2 + 1/2 ² + 1/2 ³ + ... +1/2 ^h + h / 2 ^{h + 1} }
się 1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h zmniejsza GP, którego suma jest mniejsza niż 1 (gdy h dąży do nieskończoności, suma dąży do 1). W dalszej analizie, weźmy górną granicę sumy, która wynosi 1.
To daje S = 2 ^{h + 1} {1 + h / 2 ^{h + 1} }
                    = 2 ^{h + 1} + h
                    ~ 2 ^h + h
as h = log (n) , 2 ^godz. = n

Dlatego S = n + log (n)
T (C) = O (n)

Budując stertę, powiedzmy, że stosujesz podejście oddolne.

1. Bierzesz każdy element i porównujesz go z jego dziećmi, aby sprawdzić, czy para jest zgodna z regułami sterty. Dlatego liście dołączane są do kupy za darmo. To dlatego, że nie mają dzieci.
2. Idąc w górę, najgorszym scenariuszem dla węzła tuż nad liśćmi byłoby 1 porównanie (przy maksimum byłyby one porównywane tylko z jednym pokoleniem dzieci)
3. Idąc dalej, ich najbliżsi rodzice mogą być maksymalnie porównani z dwoma pokoleniami dzieci.
4. Kontynuując w tym samym kierunku, będziesz mieć log (n) porównania dla katalogu głównego w najgorszym przypadku. i log (n) -1 dla jego bezpośrednich potomków, log (n) -2 dla ich bezpośrednich potomków i tak dalej.
5. Podsumowując, otrzymujesz coś w rodzaju log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ..... + 1 * 2 ^ {( logn) -1}, który jest niczym innym jak O (n).

W przypadku budowy hałdy zaczynamy od wysokości, logn -1 (gdzie logn jest wysokością drzewa n elementów). Dla każdego elementu obecnego na wysokości „h” przechodzimy do maksymalnej wysokości (logn-h) wysokości w dół.

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)

Kolejne wstawki można opisać przez:

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

n! =~ O(n^(n + O(1)))Dlatego przybliżając szpakT =~ O(nlog(n))

Mam nadzieję, że to pomaga, optymalnym sposobem O(n)jest użycie algorytmu budowania sterty dla danego zestawu (kolejność nie ma znaczenia).

Zasadniczo praca jest wykonywana tylko na węzłach innych niż liście podczas budowania stosu ... a wykonana praca to ilość zamiany w dół, aby spełnić warunek stosu ... innymi słowy (w najgorszym przypadku) ilość jest proporcjonalna do wysokości węzła ... w sumie złożoność problemu jest proporcjonalna do sumy wysokości wszystkich nie-liściowych węzłów .. którym jest (2 ^ h + 1 - 1) -h-1 = nh-1 = Na)

@bcorso pokazał już dowód analizy złożoności. Ale ze względu na osoby wciąż uczące się analizy złożoności muszę dodać:

Podstawa twojego pierwotnego błędu wynika z błędnej interpretacji znaczenia stwierdzenia: „wstawienie do stosu zajmuje czas O (log n)”. Wstawianie do stosu jest rzeczywiście O (log n), ale musisz rozpoznać, że n jest rozmiarem stosu podczas wstawiania .

W kontekście wstawiania n obiektów do stosu złożoność i-tego wstawienia wynosi O (log n_i), gdzie n_i jest rozmiarem stosu jak przy wstawianiu i. Tylko ostatnie wstawienie ma złożoność O (log n).

Załóżmy, że masz N elementów na stosie. Wtedy jego wysokość wynosiłaby Log (N)

Teraz chcesz wstawić inny element, to złożoność byłoby: log (N) , musimy porównać całą drogę UP do korzenia.

Teraz masz N + 1 elementów i wysokość = Log (N + 1)

Za pomocą techniki indukcyjnej można udowodnić, że złożoność wstawienia byłaby ∑logi .

Teraz używa

log a + log b = log ab

Upraszcza to: ∑logi = log (n!)

czyli tak naprawdę O (NlogN)

Ale

robimy tutaj coś złego, ponieważ we wszystkich przypadkach nie sięgamy do szczytu. Dlatego podczas wykonywania większości przypadków możemy się przekonać, że nie idziemy nawet w połowie wysokości drzewa. Skąd ta granica może być zoptymalizowana, aby mieć jeszcze ściślejszą granicę, używając matematyki podanej w odpowiedziach powyżej.

Ta realizacja przyszła do mnie po szczegółach i eksperymentach na hałdach.

Naprawdę podoba mi się wyjaśnienie Jeremy'ego Westa .... inne podejście, które jest naprawdę łatwe do zrozumienia, znajduje się tutaj http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

ponieważ budowanie zależy od użycia zależy od stosu i stosuje się podejście zmniejszające, które zależy od sumy wysokości wszystkich węzłów. Tak więc, aby znaleźć sumę wysokości węzłów, która jest dana przez S = sumowanie od i = 0 do i = h z (2 ^ i * (hi)), gdzie h = logn jest wysokością rozwiązania drzewa s, otrzymujemy s = 2 ^ (h + 1) - 1 - (h + 1), ponieważ n = 2 ^ (h + 1) - 1 s = n - h - 1 = n- logn - 1 s = O (n), i tak złożoność zestawienia kompilacji wynosi O (n).

„Liniową granicę czasową kompilacji Sterty można pokazać, obliczając sumę wysokości wszystkich węzłów w stercie, która jest maksymalną liczbą linii przerywanych. Dla idealnego drzewa binarnego wysokości h zawierającego N = 2 ^ ( h + 1) - 1 węzły, suma wysokości węzłów wynosi N - H - 1. Zatem jest to O (N). ”

Dowód O (n)

Dowód nie jest wyszukany i dość prosty, udowodniłem tylko, że jest to pełne drzewo binarne, wynik można uogólnić dla pełnego drzewa binarnego.

Czas wykonywania kompilacji sterty uzyskujemy, ustalając maksymalny ruch, jaki może podjąć każdy węzeł. Musimy więc wiedzieć, ile węzłów znajduje się w każdym rzędzie i jak daleko od nich może przejść każdy węzeł.

Zaczynając od węzła głównego, każdy następny rząd ma dwa razy więcej węzłów niż poprzedni, więc odpowiadając, jak często możemy podwoić liczbę węzłów, dopóki nie zostanie nam żaden węzeł, otrzymamy wysokość drzewa. Lub w kategoriach matematycznych wysokość drzewa wynosi log2 (n), gdzie n jest długością tablicy.

Aby obliczyć węzły w jednym rzędzie, zaczynamy od tyłu, wiemy, że n / 2 węzłów znajduje się na dole, więc dzieląc przez 2, otrzymujemy poprzedni wiersz i tak dalej.

Na tej podstawie otrzymujemy wzór na podejście Siftdown: (0 * n / 2) + (1 * n / 4) + (2 * n / 8) + ... + (log2 (n) * 1)

Termin w ostatnim nawiasie to wysokość drzewa pomnożona przez jeden węzeł znajdujący się u nasady, termin w pierwszym nawiasie to wszystkie węzły w dolnym rzędzie pomnożone przez długość, jaką mogą przebyć, 0. Ta sama formuła w smart:

Przywracając n mamy 2 * n, 2 można odrzucić, ponieważ jest to ciągłe i tada mamy najgorszy czas działania podejścia Siftdown: n.

myślę, że popełniasz błąd. Spójrz na to: http://golang.org/pkg/container/heap/ Budowanie sterty to nie O (n). Jednak wstawianie to O (lg (n). Zakładam, że inicjalizacja to O (n), jeśli ustawisz rozmiar sterty b / c, sterty muszą przydzielić miejsce i skonfigurować strukturę danych. Jeśli masz n elementów do umieszczenia do stosu, a następnie tak, każda wstawka jest lg (n) i jest n elementów, więc dostajesz n * lg (n), jak podano