Définition du tas :
n séquences de mots clés Kl, K2,...,Kn sont appelées (Heap) si et seulement si This séquence satisfait les propriétés suivantes (propriétés du tas en abrégé) : (1) ki<=k(2i) et ki<=k(2i 1)(1≤i≤n/2). Bien sûr, il s'agit d'un petit tas racine. et un grand tas racine. Le tas est remplacé par le signe >=. k(i) est équivalent au nœud non-feuille de l'arbre binaire, K(2i) est le nœud enfant gauche et k(2i 1) est le nœud enfant droit. Si le vecteur R[1..n] stocké dans cette séquence est considéré comme la structure de stockage d'un arbre binaire complet, alors le tas est essentiellement un arbre binaire complet qui satisfait les propriétés suivantes : la clé de tout nœud non-feuille dans l'arbre est un mot-clé qui n'est pas supérieur (ou pas inférieur) à ses nœuds enfants gauche et droit (s'ils existent).
/** * 调整堆 * @param array $arr 排序数组 * @param int $i 待调节元素的下标 * @param int $size 数组大小, 准确来说是数组最大索引值加1 */ function heapAjust(& $arr, $i, $size) { $key = $arr[$i]; // 索引从0开始 // 左孩子节点为 2i+1, 右孩子节点为 2i+2 for($j = 2 * $i + 1; $j < $size; $j = 2 * $j + 1) { if($j + 1 < $size && $arr[$j] < $arr[$j + 1]) $j++; if($key > $arr[$j]) break ; $arr[$i] = $arr[$j]; //调换值 $i = $j; } $arr[$i] = $key; } /** * 堆排序 * 时间复杂度:O(nlogn) * 不稳定的排序算法 */ function heapSort(& $arr) { $len = count($arr); // 构建初始大根堆 for($i = intval($len/2); $i >= 0; $i--) { heapAjust($arr, $i, $len); } // 调换堆顶元素和最后一个元素 for($j = $len - 1; $j > 0; $j--) { $swap = $arr[0]; $arr[0] = $arr[$j]; $arr[$j] = $swap; heapAjust($arr, 0, $j); //继续调整剩余元素为大根堆 } }
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!