アルゴリズムチュートリアル:ヒープへのイントロ

私はヒープデータ構造について議論しました、そして、それがどのようにシリーズのMAX/MIN値を検索するために最適化されたデータ構造を作るのに使用されて、新しい値がプライオリティキューのようなユースケースで加えられるように、速く再優先順位をつけることができます.
提案通り
先週のコメントでは、ヒープの驚くべきプロパティはここで終わらない.調べましょうheapify and heapSort . あなたがヒープ構造に慣れていないならbubbleUp and trickleDown それが必要とする操作

内容

Heapify

Three Approaches

Measuring Efficiency

Heapify Implementation

Heap Sort

Resources

MaxHeap Class Gist

強要する

heapifyは既存の順序のない配列をとる行為を記述し、ヒープ構造に変換します.このプロセスが興味をそそらせるのは、うまく実装されていれば、O(1)のスペースを意味し、O(N)、O(N)、O(N log)時間、O(N log N)時間を意味している.

三つのアプローチ

既存の配列をまとめるには、次の3つの方法をとることができます.

1) We create a new empty heap, and then iterate through the array, inserting each element of the array into this heap using the insert and bubbleUp functions described in the . The drawback to this approach, is that not only are we creating an entirely new structure to hold each value, O(n) space, we also need to iterate through each item in the array, O(n), and insert each one, O(log n), which creates an overall time complexity of O(n log n). It works, but we can do better.

我々のスペース使用を改善するために、我々は既存の配列要素を変更することによってヒープを作成し、必要に応じてこの配列内でそれらをシャフリングする必要があるbubbleUp() or trickleDown() メソッド.

2) Our first option would be to start at the first item in the array (root of the tree), and iterate through each element and invoking bubbleUp on each one. This would compare each node against its ancestors, and move it further up the tree as necessary. By the time we finish with the last element in the array, each element will have been placed accordingly and we will have our heap.

3) The other option, is to start at the bottom-most node on the tree that has children and iterate up to the root, calling trickleDown on each one. Like the previous option, this would leave each element correctly place once we finish with the root node.

上記のオプション2と3の効率を比較するために、我々は、与えられたノードのためにどれくらいの潜在的スワップが起こる必要があるかについて見るためにヒープの構造を綿密に調べなければなりません、そして、どのように多くのノードがそれらのスワップをするのに必要でありえたかもしれません.

測定効率

例として15ノードツリーを使いましょう.数学的には、任意のツリー内のタイの数を計算することができますlog n ここでNはノード数である.この場合、4段である.オプション2のアプローチを使用して、ノードの階層からルートまでの距離を見て、スワップの最悪の合計数を見つけることができました.

EX :

1ノードは0スワップ(既にルート)

ティア2上の2つのノードは、ルートに達するために1つのスワップを持つことができました

Tier 3の4つのノードは、2つのスワップを持つことができました

Tier 4の8つのノードは、3つのスワップを持っているかもしれません

ここで、木がより深くなるように、潜在的スワップの数がすぐに成長するので、ノードの半分が木の底層にあることができて、潜在的に木の全体の深さで交換する必要があるので、我々はすぐにわかることができます.最終的に、これはn/2 * log n 任意の層に対しては、オプション1のようにO ( n log n )を簡素化しますが、余分なスペースを必要としません.
比較のために、我々がオプション3と呼び出しでアプローチを使用するならばtrickleDown それぞれのノードで、「スワップ数」は16ノードツリーでは非常に異なっているでしょう.
EX :

ルートの1つのノードは、底に達するために3つのスワップを持つことができました

層2の2つのノードは、底に達するために2つのスワップを持つことができました

Tier 3の4つのノードは、1つのスワップを持つことができました

層4上の8つのノードは0スワップ(既に下側)を有する

ここで、木のノードの最高半分のために、どんな行動も必要でなくて、したがって、オプション2と2を使うより、より効率的であるでしょうbubbleUp . 数学的には、このプロセスはO ( n )時間になり、this proof provided by Jeremy West . このプロセスを使用すると、余分なスペースなしで、任意の配列をヒープにできます.

実装を高める

heapifyを効率的に実装するには、まず、子ノードを持つツリー内の最後のノードを検索する必要がありますtrickleDown そこからルートへの各々のノードのために.このノードはMath.floor((n - 2)/2) . 前のブログとは違ってtrickleDown 特定のノードで起動し、常にルートではなく、リファクタリングをしますtrickleDown 以前のポストの実装と比較して任意のパラメータを受け入れる.参照full MaxHeap class gist below のためにtrickleDown MaxHeapクラスの実装の残りの部分の実装.

class MaxHeap {
 constructor(arr = []){
    this.values = this._heapify(arr)
 }
 _heapify(arr){
    if (this.size > 0) return // Optional: Prevent overriding existing heap values
    this.size = arr.length
    /** 
    * To prevent mutating current array, copy arr with
    * this.values = [...arr]
    */
    this.values = arr 
    const nodeCount = this.size - 1
    // Finds the last node of the tree that has children
    let cIdx = Math.floor((nodeCount - 2)/2)
    /** For each node up through the root, 
    * call trickleDown
    */
    for (let i = cIdx; i >= 0; i--){
      this._trickleDown(i)
    }
    return this.values
  }
  // See gist for rest of class implementation
}

適用した場合はヒープインスタンスを生成しますarr = [17,2,36,100,7,1,19,25,3] 私たちはheapify アクション

ヒープソート

ヒープソートは、一定のスペースとO(n log n)時間を使用して配列をソートするために上記のHapifyアクションを使用するソーティングメソッドです.このソート方法には本質的に二つの段階があります.
1 )配列を評価する
2 )配列の長さを反復し、各インデックスの最大値をヒープから取り出し、配列の末尾に配置します.
上記のように既に述べたものを利用し、前の投稿からの抽出を利用すると、この動作はかなり似ています.大きな違いは、抽出中に配列から値を削除したくない点です.pop , また、毎回、配列の最後のインデックスに抽出値を移動します.代わりに、最大値をどこに配置するかを決定するインデックスポインタを使用することができますtrickleDown

  static heapSort(arr){
    const heap = new MaxHeap(arr)
    for (let i = arr.length - 1; i > 0; i--){
      // Place max at pointer position by swapping with root
      heap._swap(0,i)
      // Begin trickle at root, end before placed value
      heap._trickleDown(0, i)
    }
    return heap.values
  }

資源

以下のこれらのリソースは、このポストを置く際に役に立ちました.

Evaluating Heapify Time Complexity

Heapify & Heap Sort

Heapify Animation

クラスハイクラス

< div >