PHP implementiert den Heap-Sortieralgorithmus (Codebeispiel)

In der Informatik ist Heapsort (1964 von J. W. J. Williams erfunden) ein vergleichsbasierter Sortieralgorithmus. Heapsort kann als eine verbesserte Auswahlsortierung angesehen werden: Ähnlich wie dieser Algorithmus unterteilt er die Eingabe in sortierter Bereich und unsortierter Bereich, extrahiert die maximalen Elemente und verschiebt sie in den sortierten Bereich um den unsortierten Bereich interaktiv zu verkleinern. Zu den Verbesserungen gehört die Verwendung einer Heap-Datenstruktur anstelle einer linearen Zeitsuche, um das Maximum zu finden.

Obwohl es auf den meisten Maschinen tatsächlich etwas langsamer läuft als ein gut implementierter Quicksort, hat es den Vorteil, dass es im schlimmsten Fall eine O(n)-Laufzeit hat ist vorteilhafter. Heap-Sortierung ist ein In-Place-Sortieralgorithmus, aber keine stabile Sortierung.

Der Heapsort-Algorithmus sortiert eine Reihe zufällig angeordneter Werte. In der ersten Phase des Algorithmus werden die Array-Elemente neu angeordnet, um die Heap-Eigenschaften zu erfüllen. Bevor mit der eigentlichen Sortierung fortgefahren wird, wird zur Veranschaulichung kurz die Heap-Baumstruktur gezeigt.

Schematische Darstellung der Idee des PHP-Heap-Sortierungsalgorithmus:

Der Implementierungscode für die PHP-Heap-Sortierung lautet wie folgt:

<?php
class Node
{
    private $_i;

    public function __construct($key)
    {
        $this->_i = $key;
    }

    public function getKey()
    {
        return $this->_i;
    }
}

class Heap
{
    private $heap_Array;
    private $_current_Size;

    public function __construct()
    {
        $heap_Array = array();
        $this->_current_Size = 0;
    }

 
    public function remove()
    {
        $root = $this->heap_Array[0];
        
        $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size];
        $this->bubbleDown(0);
        return $root;
    }

   
    public function bubbleDown($index)
    {
        $larger_Child = null;
        $top = $this->heap_Array[$index]; 
        while ($index < (int)($this->_current_Size/2)) { 
            $leftChild = 2 * $index + 1;
            $rightChild = $leftChild + 1;

          
            if ($rightChild < $this->_current_Size
                && $this->heap_Array[$leftChild] < $this->heap_Array[$rightChild]) 
            {
                $larger_Child = $rightChild;
            } else {
                $larger_Child = $leftChild;
            }

            if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) {
                break;
            }

            
            $this->heap_Array[$index] = $this->heap_Array[$larger_Child];
            $index = $larger_Child;
        }

        $this->heap_Array[$index] = $top;
    }

    public function insertAt($index, Node $newNode)
    {
        $this->heap_Array[$index] = $newNode;
    }

    public function incrementSize()
    {
        $this->_current_Size++;
    }

    public function getSize()
    {
        return $this->_current_Size;
    }

    public function asArray()
    {
        $arr = array();
        for ($j = 0; $j < sizeof($this->heap_Array); $j++) {
            $arr[] = $this->heap_Array[$j]->getKey();
        }

        return $arr;
    }
}

function heapsort(Heap $Heap)
{
    $size = $Heap->getSize();
    
    for ($j = (int)($size/2) - 1; $j >= 0; $j--)
    {
        $Heap->bubbleDown($j);
    }
   
    for ($j = $size-1; $j >= 0; $j--) {
        $BiggestNode = $Heap->remove();
    
        $Heap->insertAt($j, $BiggestNode);
    }

    return $Heap->asArray();
}

$arr = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 : ";
echo implode(&#39;, &#39;,$arr );
$Heap = new Heap();
foreach ($arr as $key => $val) {
    $Node = new Node($val);
    $Heap->insertAt($key, $Node);
    $Heap->incrementSize();
}
$result = heapsort($Heap);
echo "\n排序后数组 : ";
echo implode(&#39;, &#39;,$result)."\n";

Ausgabe:

原始数组 : 3, 0, 2, 5, -1, 4, 1 
排序后数组 : -1, 0, 1, 2, 3, 4, 5

Dieser Artikel ist eine Einführung in die PHP-Heap-Sortierung. Ich hoffe, er wird Freunden in Not hilfreich sein!

Das obige ist der detaillierte Inhalt vonPHP implementiert den Heap-Sortieralgorithmus (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!