四十三庵

蔀の雑記帳

Heap

データ構造とアルゴリズム (新・情報 通信システム工学)

基本教科書を読んでわかることは書かなくて、読んでいてわからなかった点や、
実際に手動かして書いてみたコードなんかを書いています。

Heapとは

www.raywenderlich.com
ここの説明がわかりやすい。

英語の意味

  • 英語のHeapの意味は積み重ね
  • heap of moneyなど

計算量

  • 要素の追加、削除は計算量がO(logN)ですむので嬉しい
  • 最小値・最大値の探索はO(1)で済むが、それ以外の任意の要素はO(N)

Heapの性質

f:id:st43:20200411105211p:plain

  • この例はRootが最大値になるパターン
  • 子Element < 親ElementがすべてのNodeで成り立つような構造になっていれば、Heap(二分木)
  • 木の高さが同じであれば、実は入れ替えることが可能な要素もある。
  • たとえばこの例では4と2は交換可能
    • つまり二分木は要素の集合に対して、一意に定まるデータ構造ではない

f:id:st43:20200411105314p:plain

  • i番目の要素の右の子のindexはElementは2i+1, 左は2i+2で得られる。
  • (ただしrootの添字が0始まりの場合)
  • 親のindexは (i - 1) /2
    • 最初ん? と思ったが、余りは考えない

書いたコード

import Foundation

struct Heap<Element> {
    var elements = [Element]()
    let priorityFunction: (Element, Element) -> Bool

    init(elements: [Element], priorityFunction: @escaping (Element, Element) -> Bool) {
        self.priorityFunction = priorityFunction
        elements.forEach { insert(element: $0) }
    }

    // [4, 3, 2, 1]に5を挿入した時を考えてみよう
    // 末尾に要素を挿入し、親要素と比較して、大小関係によって入れ替える
    mutating func insert(element: Element) {
        elements.append(element)
        var childIndex = lastIndex()
        while rootIndex() < childIndex {
            guard let parentIndex = parentIndex(index: childIndex) else { break }
            if priorityFunction(elements[childIndex], elements[parentIndex]) == true {
                elements.swapAt(childIndex, parentIndex)
                childIndex = parentIndex
            } else {
                break
            }
        }
    }

    // rootの要素を削除し、末尾の要素をrootにし、左右の子と大小関係を比較して入れ替える
    mutating func delete() {
        var index = rootIndex()
        elements.swapAt(index, lastIndex())
        elements.removeLast()
        while index < lastIndex() {
            guard let leftIndex = leftChildIndex(index: index) else { break } // 左の子要素なし
            if priorityFunction(elements[leftIndex], elements[index]) == true {
                guard let rightIndex = rightChildIndex(index: index) else { break } // 右の子要素なし
                if priorityFunction(elements[rightIndex], elements[leftIndex]) == true {
                    elements.swapAt(index, rightIndex)
                    index = rightIndex
                    continue
                } else {
                    elements.swapAt(index, leftIndex)
                    index = leftIndex
                    continue
                }
            }
            guard let rightIndex = rightChildIndex(index: index) else { break } // 右の子要素なし(二回やってるが致し方なし)
            if priorityFunction(elements[rightIndex], elements[index]) == true {
                elements.swapAt(index, rightIndex)
                index = rightIndex
                continue
            }
            break
        }
    }

    func rootIndex() -> Int {
        return 0
    }
    
    func lastIndex() -> Int {
        return elements.indices.last!
    }

    func parentIndex(index i: Int) -> Int? {
        guard rootIndex() < i else { return nil }
        return (i - 1) / 2
    }

    func leftChildIndex(index i: Int) -> Int? {
        guard (i * 2) + 1 <= lastIndex() else { return nil }
        return (i * 2) + 1
    }

    func rightChildIndex(index i: Int) -> Int? {
        guard (i * 2) + 2 <= lastIndex() else { return nil }
        return (i * 2) + 2
    }
}

let array = [1, 2, 3, 4, 5]
//let array = (1...100).map { $0 }
var heap = Heap(elements: array, priorityFunction: >)

これ、書いてみたはいいが、ヒープソートに使おうとすると上手くいかなくて、
SACを見ながら色々修正してみたけど結局ダメだった。
(了)