ホームページ > 記事 > バックエンド開発 > PHPヒープソートアルゴリズムの詳細説明

PHPヒープソートアルゴリズムの詳細説明

墨辰丷オリジナル: 2018-05-18 14:08:321660ブラウズ

この記事では、主に PHP に実装されたヒープソートアルゴリズムを紹介し、PHP ヒープソートの原理、実装手順、および関連する操作テクニックをサンプルの形で分析します。必要な方は参考にしてください。詳細は次のとおりです。

ヒープ (heap) コンピューターサイエンスにおける特殊なタイプのデータ構造の総称であり、通常はツリー

として見ることができる配列オブジェクトです。

ヒープ {k1,k2,ki,…,kn} (ki = k2i,ki >= k2i+1), (i = 1) ,2,3,4...n/2)

ヒープについて:

ヒープ内のノードの値は、常にその親ノードの値よりも大きくも小さくもありません。ヒープは常に完全なツリーであるバイナリツリー (下記)。

最大のルートノードを持つヒープは最大ヒープまたは大ルートヒープと呼ばれ、最小のルートノードを持つヒープは最小ヒープまたは小ルートヒープと呼ばれます。

完全なバイナリツリー

ヒープのソートに関して言えば、これらの基本的な概念はインターネット上のいたるところにありますが、私は最も単純なものを選びました。。

完全なバイナリツリー: 最後のレベルを除き、各レベルのノード数が最大に達し、最後のレベルでは右側のいくつかのノードだけが欠落しています。

私は、それはまさに次の 2 つの特徴のためであると結論付けました。1. 最後の層のみが空のノードを持つことが許可され、空のノードは右側にある、つまり、葉ノードは 2 つの層にのみ表示されます。最大の層 (保存方法の規則性)

2. i>1 の場合、ツリーの親は Tree[i p 2] になります (親ノードと子ノードの値の規則性)

。

ヒープソート

ヒープソートでは、昇順には大きな上部ヒープが使用され、降順には小さな上部ヒープが使用されます。 この例では、小さな上部ヒープを降順で使用して分析します。

ヒープのソート手順は次のとおりです:

1. データ (49、38、65、97、76、13、27、50) から配列 $arr を作成します。小さなトップヒープを作成します (主な手順はコードコメントで説明します。下の図は、配列を使用して小さなトップヒープを構築するプロセスです) 3. ヒープのルート (最小要素) を交換します。最後のリーフを削除し、ヒープの長さを 1 つ減らして 2 番目のステップに進みます。4. ヒープ内にノードが 1 つだけになり、ソートが完了するまでステップ 2 ～ 3 を繰り返します。

ヒープソートの PHP 実装

//因为是数组,下标从0开始,所以,下标为n根结点的左子结点为2n+1,右子结点为2n+2;
//初始化值,建立初始堆
$arr=array(49,38,65,97,76,13,27,50);
$arrSize=count($arr);
//将第一次排序抽出来，因为最后一次排序不需要再交换值了。
buildHeap($arr,$arrSize);
for($i=$arrSize-1;$i>0;$i--){
  swap($arr,$i,0);
  $arrSize--;
  buildHeap($arr,$arrSize);
}
//用数组建立最小堆
function buildHeap(&$arr,$arrSize){
  //计算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最小值存入父结点中
  //从$index处对一个树进行循环比较,形成最小堆
  for($index=intval($arrSize/2)-1; $index>=0; $index--){
    //如果有左节点,将其下标存进最小值$min
    if($index*2+1<$arrSize){
      $min=$index*2+1;
      //如果有右子结点,比较左右结点的大小,如果右子结点更小,将其结点的下标记录进最小值$min
      if($index*2+2<$arrSize){
        if($arr[$index*2+2]<$arr[$min]){
          $min=$index*2+2;
        }
      }
      //将子结点中较小的和父结点比较,若子结点较小,与父结点交换位置,同时更新较小
      if($arr[$min]<$arr[$index]){
        swap($arr,$min,$index);
      }
    }
  }
}
//此函数用来交换下数组$arr中下标为$one和$another的数据
function swap(&$arr,$one,$another){
  $tmp=$arr[$one];
  $arr[$one]=$arr[$another];
  $arr[$another]=$tmp;
}

以下はソートの最終結果です:

PHPヒープソートアルゴリズムの詳細説明

関連記事