/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 5, Bäume: Immer einer über den anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_05_10_ArrayHeap {

    /* start bei Index 0 */
    static let capacity: Int = 10
    static var lastPos: Int = -1 // last position occupied by a value
    static var h: [Int] = Array(repeating: 0, count: capacity)

    static func swap(i: Int, j: Int) {
        let t = h[i]
        h[i] = h[j]
        h[j] = t
    }

    static func remove() -> Int {
        assert(lastPos > -1)
        let result = h[0]
        h[0] = h[lastPos]
        lastPos = lastPos-1
        bubbleDown(i: 0)
        return result
    }

    static func bubbleDown(i: Int) {
        var m: Int = 2*i
        if (2*i+1 <= lastPos) {
            if (2*i + 2 > lastPos || h[2*i+1] >= h[2*i+2]) {
                m = 2 * i + 1
            } else {
                m = 2 * i + 2
            }
            if (h[i] < h[m]) {
                swap(i: i, j: m)
                bubbleDown(i: m)
            }
        }
    }

    static func insert(e: Int) {
        assert(lastPos < capacity)
        lastPos = lastPos+1
        h[lastPos] = e
        bubbleUp(i: lastPos)
    }

    static func bubbleUp(i: Int) {
        if (i > 0 && h[(i - 1) / 2] <= h[i]) {
            swap(i: i, j:(i - 1) / 2)
            bubbleUp(i: (i - 1) / 2)
        }
    }

    static func run() {
        for x in [2, 9, 7, 6, 5, 8, 1, 3, 10, 4] {
            insert(e: x)
            print("[ \(h.map({ (x) in String(x)} ).joined(separator: ", ")) ], \(lastPos)")
        }

        print("=============")

        for _  in 1 ... 10 {
            print("-> \(remove())")
            print("[ \(h.map({ (x) in String(x)} ).joined(separator: ", ")) ], \(lastPos)")
        }
    }

}