Implementierungscode für die PHP-Heap-Sortierung

Der Heap kann als vollständiger Binärbaum betrachtet werden. Mit Ausnahme der untersten Ebene ist jede Ebene voll. Dadurch kann der Heap durch ein Array dargestellt werden, und jeder Knoten entspricht einem Element im Array.
Die Beziehung zwischen Arrays und Heaps:
Binäre Heaps werden im Allgemeinen in zwei Typen unterteilt: maximaler Heap und minimaler Heap.
Maximaler Heap: Der Elementwert jedes übergeordneten Knotens im Heap ist größer oder gleich seinem untergeordneten Knoten (falls vorhanden);

Minimaler Heap: Der Elementwert jedes übergeordneten Knotens im Heap ist kleiner oder gleich seinem untergeordneten Knoten (falls vorhanden);

Was ist Heap-Sortierung?

Heap-Sortierung (vorausgesetzt, der maximale Heap wird verwendet) besteht darin, die maximale Anzahl am herauszunehmen oben auf dem Heap und passen Sie den verbleibenden Heap weiterhin an den maximalen Heap an

Heap-Sortieralgorithmus

Aufbau eines Heaps: Der Aufbau eines Heaps ist ein Prozess, bei dem der Heap ständig angepasst wird, beginnend mit len /2 und gehe zum ersten Knoten, wobei len die Anzahl der Elemente im Heap ist. Der Prozess zum Erstellen eines Heaps ist ein linearer Prozess. Der Prozess zum Anpassen des Heaps wird immer von len/2 auf 0 aufgerufen, was o(h1) + o(h2) ... + o(hlen/2) entspricht. wobei h die Tiefe des Knotens darstellt, len /2 die Anzahl der Knoten darstellt. Dies ist ein Summierungsprozess und das Ergebnis ist linear O(n).

Anpassungsheap: Der Anpassungsheap wird beim Aufbau des Heaps und auch beim Heap-Sortierungsprozess verwendet. Die Idee der Verwendung besteht darin, den Knoten i und seine untergeordneten Knoten links (i), rechts (i) zu vergleichen und den größten (oder kleinsten) der drei auszuwählen, wenn der größte (kleine)

Wert ist nicht Knoten i, sondern einer seiner untergeordneten Knoten interagiert mit Knoten i und ruft dann den Heap-Anpassungsprozess auf. Dies ist ein rekursiver Prozess. Die zeitliche Komplexität des Prozesses zum Anpassen des Heaps hängt von der Tiefe des Heaps ab. Es handelt sich um eine Protokolloperation, da

entlang der Tiefenrichtung angepasst wird.

Heap-Sortierung: Die Heap-Sortierung wird mithilfe der beiden oben genannten Prozesse durchgeführt. Die erste besteht darin, einen Heap basierend auf Elementen zu erstellen. Nehmen Sie dann den Wurzelknoten des Heaps heraus (tauschen Sie ihn normalerweise gegen den letzten Knoten aus), setzen Sie den Heap-Anpassungsprozess mit den ersten Len-1-Knoten fort und nehmen Sie dann den Wurzelknoten erneut heraus, bis alle Knoten entfernt sind. Die zeitliche Komplexität des Heap-Sortierprozesses beträgt O(nlogn). Da die Zeitkomplexität für den Aufbau eines Heaps O(n) beträgt (ein Aufruf); die Zeitkomplexität für die Anpassung des Heaps beträgt logn und die Anpassung

dauert n-1-mal, also beträgt die Zeitkomplexität für die Heap-Sortierung O( nlogn).

Beispiel:

Ausgabe:

<?php
// PHP 堆排序算法实现、堆排序时间复杂度分析
/**
 * 堆排序
 * @param array $arr
 */
function heap_sort(array &$arr)
{
    $count = count($arr);
    // 建堆 (下标小于或等于floor($count/2)-1的节点都是要调整的节点)
    for($i = floor($count / 2) - 1; $i >= 0; $i --)
    {
        heap_adjust($arr, $i, $count);
    }
    // 调整堆
    for($i = $count - 1; $i >= 0; $i--)
    {
        //将堆顶元素与最后一个元素交换
        swap($arr,0,$i);
        heap_adjust($arr,0,$i - 1);
    }
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $a 数组下标
 * @param int $b 数组下标
 */
function swap(array &$arr, $a, $b)
{
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $start 数组下标
 * @param int $end 数组下标
 */
function heap_adjust(array &$arr, $start, $end)
{
    $temp = $arr[$start];
    //沿关键字较大的孩子节点向下筛选，这里数组开始下标识0
    for($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1)
    {
        if($j != $end && $arr[$j] < $arr[$j + 1])
        {
            $j ++;
        }
        if($temp < $arr[$j])
        {
	        //将根节点设置为子节点的较大值
	        $arr[$start] = $arr[$j];
	        $start = $j;
        }
    }
    $arr[$start] = $temp;
}
// 使用
$arr = array(8,4,2,9,3,7,1,6,5);
heap_sort($arr);
print_r($arr);

Array ( [0] => 1 [1] => 2 [2] => 3 [3 ] => 4 [4] => 6 [6] => 8 [8] =>

Insgesamt beträgt die zeitliche Komplexität der Heap-Sortierung O(nlogn). Da die Heap-Sortierung nicht auf den Sortierstatus der Originaldatensätze reagiert, beträgt ihre beste, schlechteste und durchschnittliche Zeitkomplexität O(nlogn). Dies ist offensichtlich weitaus leistungsfähiger als die O(n^2)-Zeitkomplexität von Bubbling, einfacher Auswahl und direkter Einfügung.

Heap-Sortierung ist eine instabile Sortiermethode (die Reihenfolge derselben Elemente vor und nach der Sortierung kann sich ändern).

Verwandte Empfehlungen:

Detaillierte Erklärung der Heap-Sortierung in JavaScript

Detaillierte Erklärung der Heap-Sortierung des PHP-Sortieralgorithmus

Detaillierte Erläuterung des Beispiels für einen PHP-Heap-Sortieralgorithmus

Das obige ist der detaillierte Inhalt vonImplementierungscode für die PHP-Heap-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!