Ich frage mich, was ist der Algorithmus von make_heap in C ++, so dass die Komplexität 3 * N ist? Nur die Art und Weise, wie ich einen Heap durch Einfügung von Elementen erzeugen kann, hat eine Komplexität von O (N Log N). Vielen Dank!
Sie repräsentieren den Heap als Array. Die beiden Elemente unterhalb des Elements i 'th befinden sich an den Positionen 2*i+1 und 2*i+2 . Wenn das Array n -Elemente hat, nimm jedes Element vom Ende an und lass es an die richtige Stelle im Heap "fallen". Dies ist O(n) zum Ausführen.
Warum? Nun, für n/2 der Elemente gibt es keine Kinder. Für n/4 gibt es einen Teilbaum der Höhe 1. Für n/8 gibt es einen Teilbaum der Höhe 2. Für n/16 einen Teilbaum der Höhe 3. Und so weiter. Also bekommen wir die Serie n/22 + 2*n/23 + 3*n/24 + ... = (n/2)(1 * (1/2 + 1/4 + 1/8 + . ...) + (1/2) * (1/2 + 1/4 + 1/8 + . ...) + (1/4) * (1/2 + 1/4 + 1/8 + . ...) + ...) = (n/2) * (1 * 1 + (1/2) * 1 + (1/4) * 1 + ...) = (n/2) * 2 = n . Also die Gesamtzahl von "sehe, ob ich noch einen fallen muss, und wenn ja, auf welche Weise falle ich? Vergleiche kommt zu n . Aber du bekommst Abrundung von Diskretisierung, also kommst du immer zu weniger als% co_de Es gibt% sätze von Swaps, die jeweils höchstens 3 Vergleiche erfordern (Vergleiche root mit jedem Kind, um zu sehen, ob es fallen muss, dann die Kinder untereinander, wenn der root größer als beide Kinder ist.)