[Swift]ヒップ(heap)の実装

背景

Pythonはheapに関するライブラリを提供しているので、heapの原理を知るだけで問題を解決できます.しかしswiftにはheapに関連するライブラリがありません.それを使用するには、自分で実現しなければなりません.そこで、この授業では、最小のお尻を実現しましょう(最小のお尻を実現すれば、最大のお尻は砂糖を入れます).

インプリメンテーション

まず一番小さいお尻の動きを見てみましょう.私の方法でプロセスをリストします.
1.Heapオブジェクトを作成します.
2.整数値を入力->お尻を埋める過程
3.整数値の抽出->お尻から最小値を取り出す過程
使い方は難しくありませんが、実現するには少し頭を働かさなければなりません.まずHeapクラスを作成します.

class BinaryHeap {
    
    var items = [Int]()
}

itemsという配列が生成された.ここに整数を加える.勝手に入れるとお尻じゃないとどうやって入れますか?
まず計算が簡単で、itemsの最初のインデックスは無効です.したがって、インデックス1から始めます.したがって、hipを初期化するときに、2回の初期化の値を入れます.

class BinaryHeap {
    
    var items = [Int]()
    
    init(_ val: Int) {
        items.append(val)
        items.append(val)
    }
}

挿入

次に、値を追加する番です.無条件で、インデックス1には最小の値があります.そのため、値を入力するときは、自分の親と比較して、上へ進む過程が必要です!
上の図に示すように、1番のインデックスに最小値が含まれていることを確認します.ツリーと配列の各値のインデックスを比較することで、値をどのような順序で比較すべきかがわかります.
次にitemsに値を追加するコードを見てみましょう.

func percolate_up() {
        var i = items.count-1
        var parent = Int(i / 2)
        while parent > 0 {
            if items[i] < items[parent] {
                items.swapAt(i, parent)
            }
            i = parent
            parent = Int(i / 2)
        }
    }
    
    func insert(k: Int) {
        items.append(k)
        percolate_up()
    }

まずinsert(k:)を使用してitemsに値を入れ、perculate up()で自分の両親と比較し、適切な位置に値を入れます.参考までに、浸透は「浸透」の意味であり、upであるため「上へ浸透」と理解され、すなわち上へ比較しながら値を変える意味が適切であるべきである.
Insert(k:13)の場合を考慮して,親の値10と比較する.でも13は10より大きいので変わらず、その位置に置かれます.
insert(k:7)を考慮すると、7は親値10より小さくなるため、親値と交換されます.
そして親の値6と比較し、6より大きいのでその位置にあります.

抽出

抽出の過程も難しくない.items配列にきれいに挿入され、最小値のインデックス1を抽出し、最小値を埋め込むだけでよい.

    func percolate_down(idx: Int) {
        let left = idx * 2
        let right = idx * 2 + 1
        var smallest = idx
        
        if left <= items.count-1 && items[left] < items[smallest] {
            smallest = left
        }
        
        if right <= items.count-1 && items[right] < items[smallest] {
            smallest = right
        }
        
        if smallest != idx {
            items.swapAt(idx, smallest)
            percolate_down(idx: smallest)
        }
    }
    
    func extract() -> Int {
        let extracted = items[1]
        items[1] = items[items.count-1]
        items.popLast()
        percolate_down(idx: 1)
        return extracted
    }

extract()を表示します.itemsの最初のインデックスの値が最小なので、値を抽出し、itemsの最後の値を最初のインデックスに入れます.次に、配列の最後の値を削除します.以上の手順を図に示します.
次にperculate down(idx:)で1番インデックスの値を自分の位置に移動します.このプロセスでは、1番のインデックスに最小値が含まれます.
perculat down(idx:)コードを見てみましょう.leftとrightはそれぞれ1番インデックスの左、右サブノードを表す.左ノードの値より大きい場合は最小値を左に、右ノードの値より大きい場合は最小値を右に変更します.
親ノードの値がより大きい場合は、最小値とidx位置の値を交換し、perculate downを繰り返します.

完全なコード

class BinaryHeap {
    
    var items = [Int]()
    
    init(_ val: Int) {
        items.append(val)
        items.append(val)
    }
    
    func percolate_up() {
        var i = items.count-1
        var parent = Int(i / 2)
        while parent > 0 {
            if items[i] < items[parent] {
                items.swapAt(i, parent)
            }
            i = parent
            parent = Int(i / 2)
        }
    }
    
    func insert(k: Int) {
        items.append(k)
        percolate_up()
    }
    
    func percolate_down(idx: Int) {
        let left = idx * 2
        let right = idx * 2 + 1
        var smallest = idx
        
        if left <= items.count-1 && items[left] < items[smallest] {
            smallest = left
        }
        
        if right <= items.count-1 && items[right] < items[smallest] {
            smallest = right
        }
        
        if smallest != idx {
            items.swapAt(idx, smallest)
            percolate_down(idx: smallest)
        }
    }
    
    func extract() -> Int {
        let extracted = items[1]
        items[1] = items[items.count-1]
        items.popLast()
        percolate_down(idx: 1)
        return extracted
    }
}

リファレンス

https://babbab2.tistory.com/109
https://www.cs.usfca.edu/~galles/visualization/Heap.html