PHPヒープソートの実装原理と応用方法_PHPチュートリアル

PHP ヒープ ソートの実装原理と応用方法

この記事では、主に PHP ヒープ ソートの実装原理と応用方法を詳細に分析します。参考にしてみてください

この記事の例では、PHP ヒープ ソートの実装原理と適用方法について説明します。皆さんの参考に共有してください。具体的な分析は次のとおりです:

ここでは、プログラムの可読性を確保するために、PHP を記述言語として使用しています。PHP プログラムのヒープに関するいくつかの概念は次のとおりです。

n が現在の配列のキーであると仮定すると、n の親ノードは n>>1 または n/2 (割り算可能) であり、n の左の子ノードは l= n $arr=配列(1,8,7,2,3,4,6,5,9);

配列 $arr の元の構造は次のとおりです:

1

/
8 7
//
2 3 4 6
/
5 9
ヒープソート($arr);print_r($arr);

ソート後に生成される標準的なスモールトップヒープ構造は次のとおりです:

1

/
2 3
//
4 5 6 7
/
8 9
つまり、配列: array(1,2,3,4,5,6,7,8,9):

コードは次のとおりです:

関数ヒープソート(&$arr)

{
//最後の要素ビットを検索します
$last=カウント($arr); //$arr[0] は通常、ヒープのソートでは無視されます
array_unshift($arr,0); //最後の非リーフノード
$i=$last>>1;
//大きな上部ヒープに編成し、最大数値をヒープの先頭に移動し、最大数値をヒープの末尾と交換し、後続の計算では配列の後端 (最後) の最大数値を無視します。ヒープの先頭 (last=ヒープの先頭)
その間(本当)
{
調整ノード($i,$last,$arr); if($i>1)
{
// ノード ポインタを移動し、リーフ以外のノードをすべて走査します
$i--; }
それ以外は
{
//クリティカルポイント last=1、つまりすべてのソートが完了しました
if($last==1)ブレイク
// i が 1 の場合、ヒープがソートされるたびに最大数 (ヒープの先頭、$arr[1]) が取得され、ルート ノードで繰り返しヒープが調整されることを意味します
スワップ($arr[$last],$arr[1]); // 配列の最後にサイズの順に最大数を予約し、ヒープをソートするときに配列の後ろにあるソートされた要素が再び中断されるのを避けるためにクリティカル ポイントを最後に定義します
$最後--; }
}
//最初の配列要素をポップします
配列シフト($arr); }

// 現在のツリー ノード ($n) を整理します。重要な点 $last 以降は並べ替えられた要素です
関数adjustnode($n,$last,&$arr)
{
$l=$n if(!isset($arr[$l])||$l>$last) return ; $r=$l+1; //$n の右の子ビット

//右の子が左の子より大きい場合は、親ノードの右の子を
より大きくする if($r$arr[$l]) $l=$r; //子ノード $l が親ノード $n より大きい場合、親ノード $n と交換します
if($arr[$l]>$arr[$n])
{
//子ノードの値 ($l) は親ノードの値 ($n) と交換されます
スワップ($arr[$l],$arr[$n]); //交換後も、親ノード ($n) の値 ($arr[$n]) はアトミック ノード ($l) の子ノードの値よりも小さい可能性があるため、アトミックノード ($l) は再帰を使用して実装されるように調整する必要があります
調整ノード($l,$last,$arr); }
}

//2つの値を交換します
関数スワップ(&$a,&$b)
{
$a=$a ^ $b;
$b=$a ^ $b;
$a=$a ^ $b; }



この記事で説明した内容が皆様の PHP プログラミング設計に役立つことを願っています。






http://www.bkjia.com/PHPjc/975889.html

www.bkjia.com
tru​​e

http://www.bkjia.com/PHPjc/975889.html

技術記事 PHP ヒープ ソートの実装原理と応用方法 この記事では主に PHP ヒープ ソートの実装原理と応用方法を紹介し、一定の参考になるヒープ ソートの原理と使用テクニックをより詳細に分析します...