Heap - Geben Sie einen

15

Höchstwahrscheinlich wird diese Frage schon einmal gestellt. Es ist aus CLRS (2nd Ed) Problem 6.5-8 -

Geben Sie einen -Zeitalgorithmus an, um sortierte Listen zu einer sortierten Liste zusammenzuführen, wobei die Gesamtzahl der Elemente in allen Eingabelisten ist. (Hinweis: Verwenden Sie einen Min-Heap für die Way-Zusammenführung.)O(nlgk)knk

Da es sortierte Listen und insgesamt Werte gibt, nehmen wir an, dass jede Liste Zahlen enthält. Außerdem wird jede Liste in streng aufsteigender Reihenfolge sortiert und die Ergebnisse werden auch in aufsteigender Reihenfolge gespeichert bestellen.knnk

Mein Pseudocode sieht so aus -

    list[k]   ; k sorted lists
    heap[k]   ; an auxiliary array to hold the min-heap
    result[n] ; array to store the sorted list
    for i := 1 to k                 ; O(k)
    do
        heap[i] := GET-MIN(list[i]) ; pick the first element 
                                    ; and keeps track of the current index - O(1)
    done
    BUILD-MIN-HEAP(heap) ; build the min-heap - O(k)
    for i := 1 to n
    do
        array[i] := EXTRACT-MIN(heap)   ; store the min - O(logk)
        nextMin := GET-MIN(list[1])     ; get the next element from the list 1 - O(1)
        ; find the minimum value from the top of k lists - O(k)
        for j := 2 to k                 
        do
            if GET-MIN(list[j]) < nextMin
                nextMin := GET-MIN(list[j]) 
        done
        ; insert the next minimum into the heap - O(logk)
        MIN-HEAP-INSERT(heap, nextMin)
    done

Meine Gesamtkomplexität wird . Ich konnte keinen Weg finden, die -Schleife innerhalb der -Schleife zu umgehen , um das nächste minimale Element aus k-Listen zu finden. Gibt es einen anderen Weg? Wie bekomme ich einen -Algorithmus?O ( k ) O ( n ) O ( n lg k )O(k)+O(k)+O(n(k+2lgk))O(nk+nlgk)O(nk)O(k)O(n)O(nlgk)

Ramgorur
quelle

Antworten:

13

Der Zweck des Heaps ist es, Ihnen das Minimum zu geben, daher bin ich mir nicht sicher, was der Zweck dieser for-Schleife ist for j := 2 to k.

Meine Einstellung zum Pseudocode:

lists[k][?]      // input lists
c = 0            // index in result
result[n]        // output
heap[k]          // stores index and applicable list and uses list value for comparison
                 // if i is the index and k is the list
                 //   it has functions - insert(i, k) and deleteMin() which returns i,k
                 // the reason we use the index and the list, rather than just the value
                 //   is so that we can get the successor of any value

// populate the initial heap
for i = 1:k                   // runs O(k) times
  heap.insert(0, k)           // O(log k)

// keep doing this - delete the minimum, insert the next value from that list into the heap
while !heap.empty()           // runs O(n) times
  i,k = heap.deleteMin();     // O(log k)
  result[c++] = lists[k][i]
  i++
  if (i < lists[k].length)    // insert only if not end-of-list
    heap.insert(i, k)         // O(log k)

Die Gesamtzeitkomplexität ist somit O(klogk+n2logk)=O(nlogk)

Sie können auch anstelle von deleteMinund insertein getMin( ) und ein ( O ( log k ) ) haben, wodurch der konstante Faktor, aber nicht die Komplexität verringert wird.O(1)incrementIndexO(logk)

Beispiel:
(Verwenden von Wert anstelle von Index und Listenindex und Heap, der der Übersichtlichkeit halber als sortiertes Array dargestellt wird)

Input: [1, 10, 15], [4, 5, 6], [7, 8, 9]

Initial heap: [1, 4, 7]

Delete 1, insert 10
Result: [1]
Heap: [4, 7, 10]

Delete 4, insert 5
Result: [1, 4]
Heap: [5, 7, 10]

Delete 5, insert 6
Result: [1, 4, 5]
Heap: [6, 7, 10]

Delete 6, insert nothing
Result: [1, 4, 5, 6]
Heap: [7, 10]

Delete 7, insert 8
Result: [1, 4, 5, 6, 7]
Heap: [8, 10]

Delete 8, insert 9
Result: [1, 4, 5, 6, 7, 8]
Heap: [9, 10]

Delete 9, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9]
Heap: [10]

Delete 10, insert 15
Result: [1, 4, 5, 6, 7, 8, 9, 10]
Heap: [15]

Delete 15, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9, 10, 15]
Heap: []

Done
Dukeling
quelle
Nehmen wir an, Sie müssen diese Listen zusammenführen, Liste [1] = [1, 10, 15], Liste [2] = [4, 5, 6] und Liste [3] = [7, 8, 9]. Bei der ersten Iteration ist der Wert aus dem Heap 1 und als nächstes fügt Ihr Algorithmus 10 in den Heap ein, aber 10 ist der größte Wert aller Listen - wie vermeiden Sie das?
Ramgorur
@ Ramgorur Es ist egal, dass 10 auf dem Haufen ist. 4, 5, 6, 7, 8 und 9 werden alle verarbeitet, da wir immer den kleinsten Wert aus dem Heap abrufen und gelöschte Werte durch den nächsten Eintrag aus derselben Liste ersetzen. Bearbeitete Antwort mit Beispiel.
Dukeling
Wenn dies der Fall ist, müssen wir uns nicht die gleiche Liste für den nächsten Element-Push merken . Wir können jedes Mal eine zufällige Liste auswählen und das nächste Element in den Haufen schieben - was vermutlich auch das gleiche Ergebnis liefert, oder? Oder gibt es einen anderen besonderen Grund, dem gleichen Listenargument zu folgen ?
Ramgorur
Wenn Sie beim Löschen 4eine zufällige Liste auswählen, wird möglicherweise 8der Heap eingefügt [7, 8, 10], von dem aus Sie 7statt 5in die Ergebnismenge einfügen , was falsch ist.
Dukeling
@ AshwaniGautams Kommentar zu der anderen Antwort ist passend: Das Erstellen des Heaps kann anfänglich in der Zeit . O(k)
Raphael
13

Zunächst denke ich, dass Ihre Annahme, dass alle Listen Einträge haben, nicht gültig ist, wenn die Laufzeit des Algorithmus von der Länge der längsten Liste abhängt .n/k

Für Ihr Problem sollte der folgende Algorithmus den Trick ausführen:

  1. HklmO(klgk)
  2. i1n
    • mHresult[i]O(lgk)
    • mlmHO(lgk)

O(klgk+nlgk)=O(nlgk)result

iresultHiresult[1..i]i

resultHresultr1lr1l[1]r1r1l[1]<r1r1result

iriHHmllHresultrimll

result[1..n]

Cornelius Brand
quelle
Tatsächlich wäre die engere zeitliche Komplexität O (K + 2 * NlogK) = O (NlogK) . O (K) ist bei einem Haufen enger gebunden als O (KlogK) . Siehe diese für weitere Erläuterungen.
Ashwani Gautam
O(k)O(klogk)k