PHP implementiert den Heap-Sortieralgorithmus (Codebeispiel)-PHP-Tutorial-php.cn

PHP implementiert den Heap-Sortieralgorithmus (Codebeispiel)

藏色散人

Freigeben： 2023-04-05 13:40:02

Original

2953 Leute haben es durchsucht

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.

PHP implementiert den Heap-Sortieralgorithmus (Codebeispiel)

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:

PHP implementiert den Heap-Sortieralgorithmus (Codebeispiel)

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";

Nach dem Login kopieren

Ausgabe:

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

Nach dem Login kopieren

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!