Heaps

HEA — Building a Heap

solvedbrowser + CLI Problem statement Open in the workbench Download .bl

Any permutation with the heap property is accepted, so the property is what is asserted. Floyd's construction reaches 7 3 5 1 2 where the sample shows 7 5 1 3 2.

# Rosalind: HEA — Building a Heap
# https://rosalind.info/problems/hea/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A permuted array A satisfying the binary max heap property: for any
# 2 <= i <= n, A[floor(i/2)] >= A[i].

let a = [1, 3, 5, 7, 2]

# Floyd's construction: sift down from the last internal node backwards. Doing
# it in this order is what makes building the heap linear rather than n log n —
# every subtree below a node is already a heap by the time the node is sifted.
fn sift_down(heap, start, size) {
    let xs = heap
    let root = start
    let settled = false
    while settled == false {
        let largest = root
        let left = 2 * root + 1
        let right = 2 * root + 2
        if left < size and xs[left] > xs[largest] then largest = left
        if right < size and xs[right] > xs[largest] then largest = right
        if largest == root {
            settled = true
        } else {
            let held = xs[root]
            xs[root] = xs[largest]
            xs[largest] = held
            root = largest
        }
    }
    xs
}

let heap = a
let node = int(len(heap) / 2) - 1
while node >= 0 {
    heap = sift_down(heap, node, len(heap))
    node = node - 1
}

let result = heap |> map(|v| str(v)) |> join(" ")

# Any permutation with the heap property is accepted, so the property itself is
# what gets checked. The sample output is 7 5 1 3 2; sifting down from the last
# internal node reaches 7 3 5 1 2, which satisfies the same condition.
let violations = range(1, len(heap)) |> filter(|i| heap[int((i + 1) / 2) - 1] < heap[i])

println("Result:   " + result)
println("Sample:   7 5 1 3 2")
println("Heap property violations: " + str(len(violations)))

fn test_hea_satisfies_the_heap_property() {
    assert len(violations) == 0, "HEA: heap property broken at 1-based positions " + str(violations)
    assert sort(heap) == sort(a), "HEA: the result is not a permutation of the input: " + result
}