コーディングのインタビューとアルゴリズムについていくつかの新しいリソースを通過しながら、ヒープデータ構造を使用して効率的にto doリストを優先順位付けする方法を見つけました.

ヒープ

親ノードとリーフノードを持つので、このデータ構造はバイナリツリーのようです.しかし、ノードの値を上から下へ(昇順)するので、順序は異なりますMin Binary Heap または降順Max Binary Heap ), 二項木は、左(親より少ない)と右(親より多くの)上でノードを命じます.

また、優先度や値に基づいてソートされた最上位要素を持つ主な実装であるため、HiapsもPriorityQueueと呼ばれます.ヒープクラスの最も一般的な実装方法は以下の通りです.

新しい要素を正しい位置に挿入するか、

最優先値を削除し、優先度でヒープを再編成します

これらの2つの方法はO(log n) , しかし、それを抽出せずに最上位要素を取得するだけですO(1) . 検索のためにヒープは遅くなりますO(n) したがって、すべてのデータセットで要素を見つけるのに最適なアルゴリズムではありません.空間の複雑さはO(n) ヒープの配列表現のみを格納するためです.

新しい要素を挿入する方法

一般的な情報を整理し、詳細に入りましょう.

export class MinBinaryHeap{
    constructor(){
        this.heapArray = []
    }

    insertElement(newElement){
        this.heapArray.push(newElement)

        let newElementId = this.heapArray.length - 1 

        while(newElementId > 0){ // while this id is still in the bounds of the heap array
            let newElementParentId = Math.floor((newElementId -1) /2)
            let newElementParent = this.heapArray[newElementParentId]

            if(newElementParent > newElement){
                this.swapHelper(newElementParentId, newElementId) // swap elements (found by id on this.heapArray)
                newElementId = newElementParentId // swap ids in this while loop scope
                // console.log(this.heapArray)
            }else{
                break
            }
        }
    }

    swapHelper(parentId, leafId){
        [this.heapArray[parentId], this.heapArray[leafId]] = [this.heapArray[leafId], this.heapArray[parentId]]
    }
}

いくつかの語で、我々は葉要素を親要素と比較しているので、親がより大きいならば、それがあるので、要素はスワップされますMin Binary Heap . 親インデックスが見つかった方法はMath.floor((leafIndex -1)/2) , だってrepresentation of the heap in an array follows this condition . 配列内のこの表現はINSERTメソッドをO(log n) インデックスは0に達するまで繰り返しごとに半分に分割されています.

最上位要素を返す方法とヒープを並べ替える方法

再びこのメソッドのいくつかの単語では、最優先事項を取り出し、新しい最優先事項を設定します.それで、トップアイテムがヒープ値配列から撃たれたあと、最後のアイテムは最初になります、しかし、現在、それは再配置される必要があるように、ヒープは不順です.それで、我々が各々の葉を訪問して、彼らの価値を比較して、最低が新しい親になるヒープを再配置するために.また、葉が現在存在していることを確認する必要がありますまた、最も低い値を持つ葉を交換することを確認します.

 export class MinBinaryHeap{
    constructor(){
        this.heapArray = []
    }

    pullTopElementAndReorder(){
        let topElement = this.heapArray[0]

        if(this.heapArray.length < 1) return null

        this.heapArray[0] = this.heapArray[this.heapArray.length - 1]
        this.heapArray.pop()

        this.reorderHelper()

        return topElement
    }

    reorderHelper(){
        let parentId = 0
        let leftLeafId = (parentId * 2) + 1
        let rightLeafId =  (parentId * 2) +2
        let leftLeaf = this.heapArray[leftLeafId]
        let rightLeaf = this.heapArray[rightLeafId]
        let parent = this.heapArray[parentId]

        while(!!leftLeaf && !!rightLeaf || !!leftLeaf){ //while both leaves exist or only the left leaf


            let minLeaf = Math.min(leftLeaf, rightLeaf)
            if( minLeaf < parent){ // if either one of the two leaves is less than parent swapHelper

                if(minLeaf === leftLeaf){
                    this.swapHelper(parentId, leftLeafId) // swapHelper values
                    parentId = leftLeafId // swap ids to move on down the heap
                }

                if(minLeaf === rightLeaf) {
                    this.swapHelper(parentId,rightLeafId)
                    parentId = rightLeafId
                }
            } else break

            leftLeafId = (parentId * 2) + 1
            rightLeafId =  (parentId * 2 ) + 2

            leftLeaf = this.heapArray[leftLeafId]
            rightLeaf = this.heapArray[rightLeafId]
            parent = this.heapArray[parentId]
        }
    }

    swapHelper(parentId, leafId){
        [this.heapArray[parentId], this.heapArray[leafId]] = [this.heapArray[leafId], this.heapArray[parentId]]
    }
}

トップ要素をO(1) 時間の複雑さ

    getTop(){ // O(1)
        return this.heapArray[0]
    }

todosの優先順位付け

これでHeap or PriorityQueue 実装されているだけで我々の選択の値に基づいてデータを並べ替えることができます.次に、キューに新しいtodosを追加したり、タスクを終了したり、キューから取り出したりするメソッドを使用します.
反応の実装は、今後のブログです.
または任意のアイデア/コメントでアウトを得るために歓迎、または私のチェックアウトportfolio .