Zlúčenie dvoch binárnych max haldy, v ktorých sú všetky prvky v jednej halde väčšie ako všetky prvky v druhej halde? - algoritmus, dátové štruktúry, haldy

Prišiel som s touto otázkou s programovacím rozhovorom a nie som si istý, či je moja odpoveď správna. Nepodarilo sa mi nájsť správnu odpoveď na túto otázku. Tu je otázka,

Nech H1 a H2 sú dve (binárne) max hromady s n1a n2 prvkov resp. Ak je každý prvok v H1 väčší ako každý prvok v H2, navrhnite algoritmus, ktorý spája tieto dve hromady do jednej (binárnej) max-halda v čase O (n2) (predpokladajme, že H1 aj H2 sú dostatočne veľké na to podržte n1 + n2 prvkov)

Takže som si myslel, že od každého prvku vH1 je väčšia ako každý prvok v H2, potom môžeme zlúčenú maximálnu hromadu uložiť do H1. Všetko, čo musíme urobiť, je jednoducho získať prvý prvok z H2, na pozícii 0 v poli pre H2, a potom vložiť tento prvok do H1, pripojiť na koniec poľa H1 a urobiť z neho list v H1. Môžeme to neustále robiť pre každý prvok v H2. Predpokladám, že akonáhle začneme pridávať prvky z H2 ako deti k prvkom H2, budeme musieť začať kontrolovať, či je to dieťa menšie ako rodič, a ak nie, zameníme ich. Predpokladám, že od pridania prvku bez volania heapify a výmeny v prípade potreby nám vznikne komplexita O (n2).

Je teda moje riešenie presné? Ak nie, akákoľvek pomoc bude veľmi cenená. Prosím, povedzte mi, ak je časť môjho riešenia nejasná, aby som mohol objasniť.

odpovede:

Vo všeobecnosti nemôžete iba pridať H2 do H1, pretože ako bolo zdôraznené v komentároch, môže to spôsobiť neplatnú hromadu. Táto situácia nie je nijako zvlášť zriedkavá.

Predstavte si napríklad dve maximálne hromady:

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

h1        h2

100        6
3   5
1 2 4

Ak iba pripojíte h2 k h1, získate:

    100
6    3
5 1  2 4

Čo je zjavne neplatné, pretože 4 je dieťa 3.

Ak h1 =[100,98]sa môžu stať rovnaké veci:

       100
99     6
3  5  1   2
4

Musíte pripojiť h2 k h1 a potom spustiť skratku hromada že mení usporiadanie položiek z h2 tak, aby odrážaliich nové pozície v kope. Už viete, že všetky položky, ktoré ste pridali z h2, sú menšie ako najmenšia položka v h1, takže sa nemusíte dotýkať žiadnej položky z h1.

Jediný rozdiel medzi týmto a štandardom hromada je počiatočná a konečná pozícia. V zásade začínate uprostred H2 a pracujete späť na začiatok 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
}
}

Na hromada Algoritmus sa ukázal ako O (n), kde n je počet položiek v halde, ktoré „budujete“. Pretože pracujete iba s h2.length položiek, to bude trvať O (h2.length) čas.