Scalanie dwóch binarnych maksów stert, w których wszystkie elementy w jednym stertie są większe niż wszystkie elementy w drugim? - algorytm, struktury danych, sterty

Przyszedłem na to pytanie dotyczące wywiadu programistycznego i nie jestem pewien, czy moja odpowiedź jest właściwa. Nie udało mi się znaleźć właściwej odpowiedzi na to pytanie. Oto pytanie,

Niech H1 i H2 będą dwoma (binarnymi) maksimum z n1i elementy n2 odpowiednio. Jeśli każdy element w H1 jest większy niż każdy element w H2, zaprojektuj algorytm łączący te dwa stosy w jeden (binarny) max-sterty w czasie O (n2) (załóżmy, że zarówno H1, jak i H2 są wystarczająco duże, aby przytrzymaj elementy n1 + n2)

Tak sobie myślałem, ponieważ każdy elementH1 jest większy niż każdy element w H2, wtedy możemy przechowywać scaloną maksymalną stertę w H1. Więc wszystko, co musimy zrobić, to po prostu pobrać pierwszy element z H2, w pozycji 0 w tablicy dla H2, a następnie wstawić ten element do H1, dołączyć do końca tablicy H1, czyniąc go liściem w H1. Możemy to ciągle robić dla każdego elementu w H2. Przypuszczam, że gdy zaczniemy dodawać elementy z H2 jako dzieci do elementów H2, będziemy musieli zacząć sprawdzać, czy to dziecko jest mniejsze niż rodzic, a jeśli nie, wymieniamy je. Zakładam, że ponieważ dodanie elementu bez wywołania sterty i zamiana w razie potrzeby da nam złożoność O (n2).

Czy moje rozwiązanie jest dokładne? Jeśli nie, pomoc zostanie doceniona. Powiedz mi, czy jakaś część mojego rozwiązania jest niejasna, więc mogę wyjaśnić.

Odpowiedzi:

Możesz ogólnie „po prostu dodać H2 do H1, ponieważ jak wskazano w komentarzach, zrobienie tego może spowodować powstanie nieprawidłowej sterty. Ta sytuacja nie jest szczególnie rzadka.

Na przykład wyobraź sobie dwa maksymalne sterty:

h1 = [100]
h2 = [6,3,5,1,2,4]

h1        h2

100        6
3   5
1 2 4

Jeśli po prostu dodasz h2 do h1, otrzymasz:

    100
6    3
5 1  2 4

Który jest wyraźnie nieważny, ponieważ 4 to dziecko w wieku 3 lat.

Jeśli h1 =[100,98], to samo może się zdarzyć:

       100
99     6
3  5  1   2
4

Co musisz zrobić, to dołączyć h2 do h1, a następnie uruchomić skrót sterty budowy który przestawia elementy z h2 w celu odzwierciedleniaich nowe pozycje na stercie. Wiesz już, że wszystkie przedmioty dodane z h2 są mniejsze niż najmniejszy przedmiot w h1, więc nie musisz dotykać żadnego przedmiotu z h1.

Jedyna różnica między tym a standardem sterty budowy to pozycje początkowe i końcowe. Zasadniczo zaczynasz w środku h2 i pracujesz wstecz do początku h2.

h1_length = h1.length
h2_length = h2.length
h1.array.append(h2.array)  // copies items from h2 to h1
// rearrange h2 items
start = h1_length + (h2_length/2)
for (item = start; item > h1_length; --item)
{
i = item
// This assumes that the root of the heap is at 0.
// If the root is at 1, then the left child is at i*2
while (i*2+1 < h1.length)
{
// get the largest child of this item
leftChildIndex = i*2+1
rightChildIndex = leftChildIndex + 1
largestChildIndex = leftChildIndex
if (rightChildIndex < h1.length &&
h1.array[rightChildIndex] > h1.array[leftChildIndex)
{
largestChildIndex = rightChildIndex
}
// if the item is greater than or equal to its largest child,
// then the item is where it belongs.
if (h1.array[i] >= h1.array[largestChildIndex])
{
break;
}
// swap the item with its child, and check again
swap(h1.array[i], h1.array[largestChildIndex])
i = largestChildIndex
}
}

The sterty budowy udowodniono, że algorytm to O (n), gdzie n to liczba elementów w stercie, które budujesz. Ponieważ pracujesz tylko z h2.length elementy, zajmie to czas O (h2.length).