Code d'implémentation du tri par tas PHP

Le tas peut être considéré comme un arbre binaire complet. À l'exception de la couche la plus basse, chaque niveau est plein, ce qui permet au tas d'être représenté par un tableau, et chaque nœud correspond à un élément du tableau.
La relation entre les tableaux et les tas :
Les tas binaires sont généralement divisés en deux types : le tas maximum et le tas minimum.
Tas maximum : la valeur de l'élément de chaque nœud parent dans le tas est supérieure ou égale à son nœud enfant (s'il existe)

Tas minimum : la valeur de l'élément de chaque nœud parent dans le tas ; est inférieur ou égal à son nœud enfant (s'il existe)

Qu'est-ce que le tri par tas

Le tri par tas (en supposant que le tas maximum soit utilisé) consiste à retirer le nombre maximum au niveau du nœud enfant ; en haut du tas, et continuez à ajuster le tas restant au tas maximum

Algorithme de tri du tas

Construire un tas : Construire un tas est un processus d'ajustement constant du tas, en commençant par len /2 et aller au premier nœud, où len est le nombre d'éléments dans le numéro de tas. Le processus de construction d'un tas est un processus linéaire. Le processus d'ajustement du tas est toujours appelé de len/2 à 0, ce qui équivaut à o(h1) + o(h2) ... + o(hlen/2) où h représente la profondeur du nœud, len /2 représente le nombre de nœuds. Il s'agit d'un processus de sommation et le résultat est linéaire O(n).

Tas d'ajustement : le tas d'ajustement sera utilisé dans le processus de construction du tas, et sera également utilisé dans le processus de tri du tas. L'idée d'utiliser est de comparer le nœud i et ses nœuds enfants gauche(i), droit(i), et de sélectionner le plus grand (ou le plus petit) des trois si le plus grand (petit)

la valeur n'est pas le nœud i mais l'un de ses nœuds enfants interagit avec le nœud i et appelle ensuite le processus d'ajustement du tas. Il s'agit d'un processus récursif. La complexité temporelle du processus d'ajustement du tas est liée à la profondeur du tas. Il s'agit d'une opération de connexion, car

est ajusté dans la direction de la profondeur.

Tri par tas : le tri par tas est effectué à l'aide des deux processus ci-dessus. La première consiste à construire un tas basé sur des éléments. Retirez ensuite le nœud racine du tas (généralement échangez-le avec le dernier nœud), continuez le processus d'ajustement du tas avec les premiers nœuds len-1, puis retirez à nouveau le nœud racine, jusqu'à ce que tous suppriment tous les nœuds. La complexité temporelle du processus de tri du tas est O(nlogn). Parce que la complexité temporelle de la construction d'un tas est O(n) (un appel) ; la complexité temporelle de l'ajustement du tas est logn, et l'ajustement

prend n-1 fois, donc la complexité temporelle du tri du tas est O(nlogn).

Exemple :

Sortie :

<?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] => 5 [5] => 6 [6] => 8 [8] => 9 )

Analyse de la complexité temporelle

Dans l'ensemble, la complexité temporelle du tri par tas est O(nlogn). Étant donné que le tri par tas n'est pas sensible à l'état de tri des enregistrements d'origine, sa complexité temporelle meilleure, pire et moyenne est O(nlogn). C'est évidemment bien meilleur en termes de performances que la complexité temporelle O(n^2) du bouillonnement, de la sélection simple et de l'insertion directe.

Le tri par tas est une méthode de tri instable (l'ordre des mêmes éléments avant et après le tri peut changer).

Recommandations associées :

Explication détaillée du tri des tas en JavaScript

Explication détaillée du tri des tas de l'algorithme de tri PHP

Explication détaillée de l'exemple d'algorithme de tri de tas PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!