Today I Learned

この間Pythonでアルゴリズムを勉強していたので、「今はこの資料構造を使ったほうがいい」と話しています.と思っていたのですが、どんな原理で動いているのかよく理解して使うことができませんでした.様々な資料構造の中でHIP資料構造が比較的難しいと考えて整理した.

heap(hip)とは?

hipは優先度キューの一種であり、ルートノードは最も優先度の高い値を有し、次いで優先度の高いレベルであり、逆ソート(ばらばらソート)状態を有する.O(log(N))の時間複雑度で最高値と最高値を求めることができます.
作った値段はとても有利だ.
また,完全なバイナリツリー構造を有するため,配列により実現できる利点もある.

臀部の動作過程と実施

キューとは異なり、hipには構造化された実装方法はありません.通常はクラスを使用して実装されます.

interface HeapInterface {
  heap: Array<number | null>;
}

class Heap implements HeapInterface {
  heap: Array<number | null>;
  constructor() {
    this.heap = [null];
  }
  
  // ...
}

最初のスペースを任意に空にすると、サブインデックスを簡単に取得できますが、タイプチェックが徹底したタイプスクリプトの特性のため、徹底したtype guardを行わないと、巨大なlinteErrorが発行されます.例えばそうです.

  // ...
   heappush(value: number) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);
    
    // null type이 아님을 증명하기 위해 as number를 사용했으나, 이는 좋은 방법이 아니다..
    while (parentIndex) {
      if (
        (this.heap[currentIndex] as number) < (this.heap[parentIndex] as number) 
      ) {
        // ...
      }
      break;
    }
  }

様々な資料構造が反映されたPythonがよく使われていたので、なるべくPythonライブラリを使うことにしました.
お尻は大きく分けて2つの方法があります.お尻の位置合わせのためにheapify()の方法を実現できますが、今回はスキップします.

heappush()

heappop()

お尻に値を挿入(heappush)

1.お尻の最後にエレメントを挿入します.
2.挿入ノードの親ノードを比較し、子ノードの優先度が高い場合は位置を交換します.

// ...
function heappush(heap: Array<number>, value: number) {
  heap.push(value);
  _shiftdown(heap, 0, heap.length - 1);
}

Pythonコードを見ると、push関数の内部にインデックスシフト関数が単独で実現されていることがわかります._shiftdown関数は、現在のインデックスの値を親ノードの値と比較し、優先度が高い場合は親ノードと交換する関数です.

// ...
function _shiftdown(heap: Array<number>, startpos: number, pos: number) {
  const newItem = heap[pos];
  while (startpos < pos) {
    let parentpos = (pos - 1) >> 1;
    let parent = heap[parentpos];
    if (newItem < parent) {
      heap[pos] = parent;
      pos = parentpos;
      continue
    }
    break
  }
  heap[pos] = newItem;
}

初めて見ると分かりにくいコードです.このように簡潔に書くためには,コード審査プロセスの継続的な努力と継続が必要であることを再認識した瞬間である.
1.追加したアイテムをnewItem変数に保存します.
2.parentposに遡り、newItemとparentのサイズ比較を行います.
3.newItemがparentより小さい場合、現在のheap[pos]の位置をparentに変換します.

お尻から要素を除去(heapppop)

1.heap配列の最初のノードを返します.
2.heap配列の最後のノードをルートノードに挿入します.
3.ルートノードとサブノードを比較し、優先度に応じて値を置き換えます.

function heappop(heap: Array<number>) {
  const lastelt = heap.pop(); // type: number | undefined
  
  // lastelt가 undefined거나 heap이 비어있다면 lastelt는 root노드가 되므로 더 진행할 필요가 없다
  if (heap.length && lastelt) {
    const ret = heap[0];
    heap[0] = lastelt;
    _shiftup(heap, 0);
    return ret;
  }
  return lastelt;
}

heappush()関数と同様に、Pythonライブラリは_shiftup()関数で交換プロセスを委任します.「簡潔なコードがこんなものだったことを改めて感じました」

function _shiftup(heap: Array<number>, pos: number) {
  let startpos = pos;
  let endpos = heap.length;
  let childpos = startpos * 2 + 1;
  const newItem = heap[pos];
  while (pos < endpos) {
    let rightpos = childpos + 1;
    
    // 자식간 우선순위를 비교하여 더 낮은 값과 치환해야 한다.
    if (rightpos < endpos && !(heap[childpos] < heap[rightpos])) {
      childpos = rightpos;
    }
    
    // 이미 다음 레벨 우선순위가 차우선순위이므로 root를 끝까지 탐색하여 재배치
    heap[pos] = heap[childpos];
    pos = childpos;
    childpos = childpos * 2 + 1;
  }
  heap[pos] = newItem;
  
  
  /**
   * while 문에서는 두 자식 노드간 대소만 비교하였으므로
   * shiftdown 함수를 통해 다시 우선순위에 맞게 재정렬
   */
  _shiftdown(heap, startpos, pos);
}

shiftup()もshiftdown()と同様にposの値を下に送信する.しかし,shiftup()の主な目的は,左子と右子の値を比較することによって優先度を決定する役割がより大きいことである.実際には、既存のルート値とchild値を比較する論理はshiftup()ではない.最下位レベルに下がった後、_shiftdown()関数によって適切な位置が見つかった.時間的複雑さの観点から,これは損失である可能性があるが,コードを簡潔に記述できるため,この構造を選択した.(大脳皮質)

の最後の部分

Pythonのライブラリを開き、実装クラスを必要とせず、関数を使うだけでhipを実現できます.実際にはheapqライブラリしか使用したことがありませんが、heapqライブラリを使用するのは初めてなので、関数作成の視野を広げることができます.これらのコメントプロセスにより、より簡潔なコードの作成を引き続き練習します.

まだあります。

次のバージョンでC++STLのように内蔵された資料構造が欲しい!!

ソース

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html