Detaillierte Erklärung der PHP-Heap-Sortierung

Heapsort bezieht sich auf einen Sortieralgorithmus, der eine Datenstruktur wie einen gestapelten Baum (Heap) verwendet. Es handelt sich um eine Art Auswahlsortierung. Sie können die Eigenschaften von Arrays nutzen, um das Element schnell an einem angegebenen Index zu finden. Der Heap ist in einen großen Root-Heap und einen kleinen Root-Heap unterteilt, bei denen es sich um einen vollständigen Binärbaum handelt. Die Anforderung eines großen Root-Heaps besteht darin, dass der Wert jedes Knotens nicht größer ist als der Wert seines übergeordneten Knotens, d. h. A[PARENT[i]] >= A[i]. Bei der nicht absteigenden Sortierung eines Arrays muss ein großer Root-Heap verwendet werden, da gemäß den Anforderungen eines großen Root-Heaps der Maximalwert oben im Heap liegen muss.

Definition von Heap

Wenn in einem vollständigen Binärbaum ein übergeordneter Knoten immer größer oder gleich (kleiner oder gleich) jedem untergeordneten Knoten ist, handelt es sich um einen Big-Top-Heap ( kleiner oberer Haufen).

Heap-Array-Speichermethode

Ein vollständiger Binärbaum eignet sich für die sequentielle Speicherung, sodass ein Array als vollständiger Binärbaum betrachtet werden kann.

• Knotennummerierung: Beginnen Sie mit der Wurzel des Baums, von der oberen Ebene zur unteren Ebene, von links nach rechts auf jeder Ebene, nummerieren Sie alle Knoten der Reihe nach, um eine lineare Reihenfolge zu erhalten spiegelt die gesamte binäre Baumstruktur wider.

• Nummerierungsfunktionen:

Beginnen Sie einfach mit der Nummer eines Knotens Die Knotennummern seiner Eltern, linken und rechten Kinder, Brüder usw. werden abgeleitet. Angenommen, der Knoten mit der Nummer i ist ki (1≤i≤n), dann gilt:

　①Wenn i>1, dann ist die übergeordnete Nummer von ki i/2; wenn i=1, dann ist Ki Der Wurzelknoten hat keine übergeordneten Knoten.

②Wenn 2i≤n, dann ist die Zahl des linken Kindes von Ki 2i; andernfalls hat Ki kein linkes Kind, das heißt, Ki muss ein Blatt sein. Daher muss der Knoten mit der Nummer i>n/2 im vollständigen Binärbaum ein Blattknoten sein.

③Wenn 2i+1≤n, dann ist die Zahl des rechten Kindes von Ki 2i+1; andernfalls hat Ki kein richtiges Kind.

Hinweis: Wenn ki (0≤i≤n) den Array-Index erfüllt, sind die möglichen linken und rechten Kinder 2i+1 bzw. 2i+2.

Die Idee der Heap-Sortierung (am Beispiel des Big-Top-Heaps)

Unter Verwendung der Funktion, dass der obere Teil des Heaps das größte Schlüsselwort aufzeichnet, werden in jeder Runde die oberen Elemente von Der Heap wird genommen und in den geordneten Bereich gelegt. So wie bei der Auswahlsortierung in jeder Runde ein Maximalwert ausgewählt und in den geordneten Bereich gelegt wird, kann die Heap-Sortierung als eine Verbesserung der Auswahlsortierung angesehen werden.

1. Konstruieren Sie die anfängliche Sequenz der zu sortierenden Schlüsselwörter (R0, R1, R2...Rn) in einem großen oberen Heap, dem anfänglichen ungeordneten Bereich

2. Tauschen Sie das oberste Element R[0] mit dem letzten Element R[n] aus und erhalten Sie einen neuen ungeordneten Bereich (R0, R1, R2,...Rn-1) und den neuen geordneten Bereich ( Rn);

3. Da die neue Spitze des Heaps R[0] nach dem Austausch möglicherweise die Natur des Heaps verletzt, ist es notwendig, den aktuellen ungeordneten Bereich (R0, R1) zu aktualisieren , R2,...Rn-1) werden an den neuen Heap angepasst.

Wiederholen Sie die Schritte 2 und 3, bis die Anzahl der Elemente im geordneten Bereich n-1 beträgt. Dann ist der gesamte Sortiervorgang abgeschlossen.

Algorithmusanalyse

Filteralgorithmus

//Der am schwierigsten zu verstehende Teil

• Ziel: Ein vollständiger Binärbaum, in dem alle Teilbäume Heaps sind. Dies bedeutet, dass der einzige Unterschied zwischen diesem Binärbaum und dem Knoten darin besteht, dass er die Heap-Struktur nicht erfüllt. //Sehr wichtig, sehr wichtig, sehr wichtig

Wie unten gezeigt:

• Methode: Erstens Setzen Sie die Wurzel mit den Wurzelknoten ihres linken und rechten Teilbaums und tauschen Sie das größte Element gegen den Wurzelknoten aus. Anschließend wird es entlang des zerstörten Pfads angepasst, bis der Blattknoten erhalten wird.

• Anwendung: 1. Basierend auf der oben erwähnten Heap-Sortieridee wird in den Schritten 2-3 der ungeordnete Bereich verwendet bei der Anpassung an den Haufen.

2. Initialisieren Sie den Heap

Initialisieren Sie den Heap

vom letzten Nicht-Blattknoten i (i=n/2, n ist der Anzahl der Knoten) Zunächst wird der Binärbaum mit i als Wurzelknoten durch Filterung in einen Heap umgewandelt. Am Beispiel des ersten Bildes lautet die Nummerierungsreihenfolge 8, 7, 6 ... 1.

Die Korrektheit des Screening-Algorithmus ist ab dem letzten Nicht-Blattknoten garantiert, da das Ziel des Screening-Algorithmus ein vollständiger Binärbaum ist, in dem alle Teilbäume Heaps sind.

php实现堆排序：
<?php
//堆排序，对简单排序的改进
  function swap(array &$arr,$a,$b)
  {
      $temp=$arr[$a];
      $arr[$a]=$arr[$b];
      $arr[$b]=$temp;
  }
  //调整$arr[$start]的关键字，$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆（根节点最大的完全二叉树）
  //注意：这里节点s的左右孩子是 2*s +1 和 2*s+2(数组开始下标为0时)
   function HeapAdjust(array &$arr $start $end)
   {
       $temp= $arr[$start];
       //沿关键字较大的孩子节点向下筛选
       //左右孩子计算 （这里数组的开始下标为0）
       //左边孩子 2*$start+1,右边孩子 2*$start+2
       for ($j=2*$start+1; $j <=$end; $j=2*$j+1) { 
           if ($j !=$end &&$arr[$j] <$arr[$j+1]) {
               $j++;  //转化为右边孩子
           }
           if ($temp >=$arr[$j]) {
               break;  //已经满足大根堆
           }
           //将根节点设置为子节点的较大值
           $arr[$start]=$arr[$j];
           //继续往下
           $start=$j;
       }
       $arr[$start] =$temp;
   }
   function HeapSort(array &$arr)
   {
       $count=count($arr);
       //先将数据结构造成大根堆 （由于是完全二叉树，所以这里用floor($count/2-1),下标小于或等于这个数的节点都是有孩子的节点)
       for ($i=floor($count /2)-1; $i >=0 ; $i--) { 
           HeapAdjust($arr,$i,$count);
       }
       for ($i=$count-1; $i >=0 ; $i--) { 
       //将堆顶元素与最后一个元素交换，获取到最大元素(交换后的最后一个元素)，将最大元素放到数组末尾
           swap($arr,0,$i);
       //经过交换，将最后一个元素（最大元素）脱离大根堆，并将未经排序的新数（$arr[0...$i-1]）重新调整为大根堆
           HeapAdjust($arr,0,$i-1);
       }
   }
   $arr=array(4,1,5,9);
   HeapSort($arr);
   v

Verwandte Empfehlungen:

PHP-Heap-Sortierung-Implementierungscode

Detaillierte Erklärung der Heap-Sortierung in JavaScript

Detaillierte Erläuterung des PHP-Sortieralgorithmus Heap-Sortierung

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung der PHP-Heap-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!