import Foundation

// Binary Heap Operations & Heapsort - attempt 3
/* Purpose of this attempt
 * I had to use countless videos and blogs to finally understand Binary Heaps and Heapify.
 * So let see if I understand it strong enough to program it from scratch.
 */

let shuffled = [100,40,50,10,15,50]

print("Original:", shuffled)

helper(shuffled) // start

func helper(_ array: [Int]) -> [Int] {
    var temp = array
    // heapify
    for i in (0 ... temp.count/2).reversed() {
        heapify(&temp, i: i)
    }
    print("Sorted:  ", temp)

    insert(&temp, value: 40)
    print("Insert:  ", temp)


    return temp
}

func insert(_ array: inout [Int], value: Int) {
    array.append(value)
    for i in (0 ... array.count/2).reversed() {
        heapify(&array, i: i)
    }
}

// Returns a max heap array
// i is the parent
func heapify(_ array: inout [Int], i: Int) {
    let left = 2 * i // left node
    let right = 2 * i + 1 // right node
    var max = 0

    print("For parent i: [\(i)] = \(array[i])")
    print("    left \(left) | right \(right)")


    // check if a[left] is larger than a[i]
    if left <= array.count-1 && array[left] > array[i] {
        max = left
    } else {
        max = i
    }

    //    check if a[right] is larger than a[max]
    if right <= array.count-1 && array[right] > array[max] {
        max = right
    }

    if max != i { // if i (parent) is not the max swap
        array.swapAt(i, max)
        heapify(&array, i: max)
    }
}