/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 7, Sortieren
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_07_06_SortWithPrioritiyQueue {

    class PriorityQueue {// Position 0 bleibt frei
        var H: [Int]
        var n: Int

        init(size: Int) {
            H = [Int](repeating: 0, count:size+1)
            n = 0 // Index des letzten Elements (0 ist unbelegt)
        }

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

        func push(x: Int) {
            H[n+1]  =  x
            var i: Int = n+1
            while (i > 1 ) {
                let p: Int  =  i/2
                if (H[i] >= H[p] ) {
                    break
                } else {
                    swap(i: i, j: p)
                    i = p
                }
            }
            n = n+1 // !!
        }

        func extractMin() -> Int {
            let x  =  H[1]
            H[1]  =  H[n]
            var i = 1
            while (i <= n ) {
                var m = i
                if  ( (2*i < n) && (H[2*i] < H[m]) ) {
                    m = 2*i
                }
                if ( (2*i+1 < n) && (H[2*i+1] < H[m]) ) {
                    m = 2*i+1
                }
                if (m == i) {
                    break
                } else {
                    swap(i: m, j: i)
                    i = m
                }
            }
            n = n-1 // !!
            return x
        }
    }


    static func PriorityQueueSort(a: inout [Int], l: Int, r: Int) {
        let Q = PriorityQueue(size: (r-l)+1)
        for  i in l ... r {
            Q .push(x: a[i])
        }
        for i  in l ... r {
            a[i] = Q.extractMin()
        }
    }

    static func run() {
        var aInt: [Int] = [6,8,0,2,3,9,7,5,1,4]

        PriorityQueueSort(a: &aInt, l: 0, r: aInt.count-1)

        print(aInt.map({ (x) in String(x)} ).joined(separator: ", "))
    }

}