Saturday, July 30, 2016

if array is in heap property

//dfs
isminheap(a):
    if a == null:
        throw
    return isminheap(a, 0)
isminheap(a, i):
    if i >= a.length():
        return true
    left = i * 2 +1
    right = left +1
    if (left < a.length() && a[i] > a[left])
        || (right < a.length() && a[i] > a[right]):
        return false
    if !isminheap(a, left):
        return false
    if !isminheap(a, right):
        return false
    return true
//bfs
isminheap(a):
    if a == null:
        throw
    result = true
    q = new
    q.enqueue(0)
    while !q.isempty():
        i = q.dequeue()
        left = i * 2 +1
        right = left +1
        if left < a.length():
            if a[i] > a[left]:
                result = false
                break
            else:
                q.enqueue(left)
        if right < a.length():
            if a[i] > a[right]:
                result = false
                break
            else:
                q.enqueue(right)
    return result

No comments:

Post a Comment