Wypisuje największe elementy K w danej stercie w O(K * log (K))?

Szukanie elementu w stercie o rozmiarze N nie jest O (K). Po pierwsze, nie ma sensu, aby złożoność czasowa znalezienia jednego elementu zależała od liczby elementów, które próbujesz wyodrębnić (czyli tego, co reprezentuje K). Ponadto, nie ma czegoś takiego jak wyszukiwanie w stercie-chyba że liczysz standardowe szukanie każdego elementu w O (N).

Jednak znalezienie największego elementu w stercie jest O (1) przez projekt (oczywiście zakładam, że jest to max-sterta, więc maksymalny element znajduje się na szczycie sterty), a usunięcie największego elementu ze sterty o rozmiarze N to o(log(N)) (zastąp go elementem liścia, a ten liść będzie perkolowany z powrotem w dół sterty).

Tak więc wyodrębnienie elementów K ze sterty, i zwrócenie sterty nieekstrahowanych elementów zajęłoby Czas O(K·log(N)).

Co się stanie, jeśli wyciągniesz z sterty elementy K nieniszcząco? Możesz to zrobić, zachowując stertę-of-heaps (gdzie wartość sterty jest wartością jego maksymalnego elementu). Początkowo ta sterta zawiera tylko jeden element (oryginalną stertę). Aby wyodrębnić następny element maksymalny, należy wyodrębnić górną stertę, wyodrębnić jej górny element (który jest maksymalnym), a następnie ponownie włożyć dwie pod-sterty z powrotem do sterty-of-sterty.

To zwiększa stertę Stert o jeden przy każdym usunięciu (usuń jeden, dodaj dwa), co oznacza, że nigdy nie będzie zawierać więcej niż K elementów , a więc remove-one-add-two zajmie O(log(K)). Jeśli to powtórzymy, otrzymamy rzeczywisty algorytm O(K·log(K)), który zwraca górne elementy K, ale nie jest w stanie zwrócić sterty nie wyodrębnionych elementów.

Znalazłem inne odpowiedzi mylące, więc postanowiłem wyjaśnić to za pomocą rzeczywistego przykładu. Załóżmy, że oryginalna sterta ma rozmiar N i chcesz znaleźć największe elementy kth, Rozwiązanie to zajmuje O (klogk) czas I O (k) przestrzeń.

    10 
   /  \
  5    3 
 / \   /\
4   1 2  0
Original Heap, N = 7 

Chcę znaleźć piąty co do wielkości element. k = 5 Uwaga: w nowej stercie należy zapisać wskaźnik do oryginalnej sterty. Oznacza to, że nie usuwasz ani nie zmieniasz oryginalnej sterty. Oryginalna sterta jest tylko do odczytu. Dlatego nigdy nie musisz robić żadnych operacje wymagające czasu o (logN).

Niech X ' będzie wskaźnikiem do wartości x w oryginalnej stercie.

Pierwsza iteracja: Get root node ' s pointer into new heap

Krok 1: Dodaj wskaźnik do węzła 10

 10'
 New Heap, size = 1, root = 10', root->left = 5, root right->3

Drukuj pierwszy największy element = 10

Druga iteracja: odnoś się do oryginalnej sterty i wstaw oba jej dzieci do nowej sterty. (Przechowywanie wskaźników do nich, a nie samej wartości). Powodem, dla którego chcesz przechowywać wskaźnik, jest to, że może uzyskać dostęp do nich w O(1) z oryginalnej sterty później, aby wyszukać ich dzieci zamiast O(N), aby wyszukać, gdzie ta wartość znajduje się w oryginalnej stercie.

Krok 2a: poszukaj lewego potomka węzła głównego nowej sterty z oryginalnej sterty. Dodaj wskaźnik dla lewego potomka (w tym przypadku 5') do nowej sterty.

  10' 
 /
5'
New Heap, size = 2, root = 10', root->left = 5, root right->3

Krok 2b: poszukaj prawego potomka węzła głównego nowej sterty z oryginalnej sterty. Dodaj wskaźnik dla lewego potomka (w tym przypadku 3') do nowej sterty.

  10' 
 / \
5'  3'
New Heap, size = 3, root = 10', root->left = 5, root right->3

Krok 2c: Usuń węzeł główny z nowej sterty. (Zamień maksymalny węzeł z prawym mostem, Usuń węzeł główny i bańka w dół bieżącego korzenia, aby zachować właściwość sterty)

  10'   swap    3'  remove & bubble   5'    
 / \     =>    / \       =>          /
5'  3'        5'  10'               3'
New Heap, size = 2, root = 5', root->left = 4, root right->1

Drukuj drugi największy element = 5

Krok 3a: poszukaj lewego potomka węzła głównego nowej sterty z oryginalnej sterty. Dodaj wskaźnik dla lewego potomka (w tym przypadku 4') do nowej sterty.

  5'
 / \
3'  4'
New Heap, size = 3, root = 5', root->left = 4, root right->1

Krok 3b: poszukaj prawego potomka węzła głównego nowej sterty z oryginalnej sterty. Dodaj a wskaźnik dla lewego potomka (w tym przypadku 1') do nowej sterty.

    5'
   / \
  3'  4'
 /
1'
New Heap, size = 4, root = 5', root->left = 4, root right->1

Krok 3c: Usuń węzeł główny z nowej sterty. (Zamień maks. węzeł (5') nowej sterty z jej prawym górnym rogu, pozostawiając większość z oryginalnej sterty (1') z nowej sterty, Usuń węzeł główny i bańkę w dół bieżącego katalogu głównego, aby zachować właściwość sterty)

    5'        Swap     1' remove & bubble     4'
   / \         =>     / \       =>           / \
  3'  4'            3'   4'                 3'  1'
 /                 / 
1'                5'
New Heap, size = 3, root = 4', root->left = NULL, root right->NULL

Drukuj trzeci co do wielkości element = 4

Krok 4a i krok 4b nic nie robią, ponieważ węzeł root nie ma w tym przypadku dzieci z original heap.

Krok 4c: Usuń węzeł główny z nowej sterty. (Zamień maksymalny węzeł z prawym most leave, Usuń węzeł główny i bańka w dół bieżącego korzenia, aby utrzymać właściwość sterty w Nowej stercie)

    4'        Swap     1' remove & bubble     3'
   / \         =>     / \       =>           / 
  3'  1'            3'   4'                 1'  
New Heap, size = 2, root = 3', root->left = 2, root right->0

Drukuj czwarty największy element = 3

Krok 5a: poszukaj lewego potomka węzła głównego nowej sterty z oryginalnej sterty. Dodaj wskaźnik dla lewego potomka (w tym przypadku 2') do nowej sterty.

     3'
    / \
   1'  2'
New Heap, size = 3, root = 3', root->left = 2, root right->0

Krok 5b: poszukaj prawego potomka węzła głównego nowej sterty z oryginalnej sterty. Dodaj wskaźnik dla pozostawione dziecko (w tym przypadku 0') do nowej sterty.

     3'
    / \
   1'  2'
  /
 0'
New Heap, size = 4, root = 3', root->left = 2, root right->0

Krok 5c: Usuń węzeł główny z nowej sterty. (Swap max node (3') z jego prawa większość opuszcza oryginalną stertę (która jest 0') w Nowej stercie, usuwa węzeł główny i bańka w dół bieżącego katalogu głównego, aby utrzymać właściwość sterty w Nowej stercie)

     3'    Swap        0'  Remove & Bubble      2'
    / \     =>        / \         =>           / \
   1'  2'            1'  2'                   1'  0'
  /                 /
 0'                3'
New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL

Drukuj piąty największy element = 2

Wreszcie, ponieważ przeszliśmy przez iteracje k , k = 5. Możemy teraz wyodrębnić wartość elementu głównego z nowej sterty. W tym przypadku, wartość to 2. Dlatego znaleźliśmy największą wartość kth z oryginalnej sterty.

Złożoność czasu, T (N, k) = O (klogk) Złożoność przestrzeni, S (N, k) = O(k)

Mam nadzieję, że to pomoże!

Soon Chee Loong,

Rzeczywiście, jest to zbyt łatwe, wydobywanie elementu max jest O(log(N)) gdzie N jest wielkością sterty. i N≠K.

Dodam, że szukanie elementu losowego to O(N) a nie O(Log(N)), ale w tym przypadku chcemy wyodrębnić max.

It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time.

steps:-

1.construct another max heap name it auxiliary heap
2.add root element of main heap to auxiliary heap
3.pop out the element from auxiliary heap and add it's 2 children to the heap
4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap.