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

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

経験 私が働いていた会社の面接の際、技術的な面に圧倒されました。基本的なデータ構造やその他の基礎に関する知識は本当に乏しかったのですが、最終的にはデザイナーになりたいと思っていました。 。 。ただし、PHP はそこそこ書けるのでインターンシップに参加することはできますが、それでも基礎をしっかりと磨きたいと思っています。 実際、私は以前から基礎の重要性を感じていましたが、より深い内容のいくつかは比較的低レベルであり、それらをしっかりと学ばなければ先に進むことはできません。たとえば、以前は PHP を使用して WebSocket を作成していましたが、データ パケットやデータ フレームなどの概念が理解できず、後で補わなければならないデータを処理することもできませんでした。だから私はデータ構造、アルゴリズム、ネットワークなどの基礎的な知識を学び直すつもりです。そして、皆さんにも私のように逆方向に進まないでください。理解するまでは手遅れです。

今日は、ヒープソートの質問について話しましょう。それについて尋ねられたとき、私は完全なバイナリツリーの概念さえ忘れていました。幸いなことに、私はまだデータ構造の基礎を少し持っており、いくつかの情報を読んだ後、それをある程度理解しました。そこで、PHP を使用してヒープのようなバイナリ ツリーを作成したいと考えています。ちなみに、バイナリ ツリーやヒープについてもレビューします。およびその他のデータ構造。

ヒープ

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

として表示できる配列オブジェクトです。 ヒープ {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ヒープソートアルゴリズム例の詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。