#!/usr/bin/python

# Let A be an array of size n > 1. The we have the following translation
# between the set H = {1, ..., n} of "heap indices" and the set I = {0,...,n-1}
# of "array indices". Let h in H denote a heap index an dlet the corresponding
# array index by i in I. We then have

def ai (h, n):
    if h<1 or h> n:
        raise NameError('Heap index out of bounds')
    else:
        return (h-1) # = i the corresponding array index


def hi (i, n):
    if i<0 or i> n-1:
        raise NameError('Array index out of bounds')
    else:
        return (i+1) # = h the corresponding heap index


# The above functions satisfy the following equations
#
#             Forall i in I: ai(hi(i)) = i
#
#             Forall h in H: hi(ai(h)) = h

# We follow Cormen, Leiserson and Rivest for the rest of the algorithm

# The following functions are expressed in terms of heap indices

def left (h, n):
    if h<1 or h > n//2:
        raise NameError('No Left Child Index')
    else:
        return (2*h)      # for all h in {1,..., n div 2}

def right (h, n):
    if h<1 or h > (n-1)//2: # if h > (n-1)// 2 then 2*h + 1 > n
        raise NameError('No Right Child Index')
    else:
        return (2*h + 1) # for all h in {1,..., n div 2}

def parent (h, n):
    if h<2 or h > n: # h = 1 is the root 
        raise NameError('No Parent Index')
    else:
        return (h//2)   # for all h in {2,..., n}

# We may translate these into functions of array indices as follows

def Left (i, n):
    return (ai (left (hi(i, n), n), n)) # for all i in {0,..., (n div 2) - 1}

def Right (i, n):
    return (ai (right (hi(i, n), n), n)) # for all i in {0,..., (n div 2) - 1}

def Parent (i, n):
    return (ai (parent (hi(i, n), n), n)) # for all i in {1,..., n-1}


def swap (A, i, j):
    s = len (A)
    if (i in range(s)) and (j in range(s)): 
        t = A[i]
        A[i] = A[j]
        A[j] = t
    else:
        raise NameError('Array index out of bounds')

def heapifyTailRecursive (A, h, s): # Heapify the array slice A[ai(1, s)..ai(s,s)]
    # Heap property: Forall j in {1,...,s}: A[Parent(j)] >= A[j] where
    # size (A) = s
    # Assuming that A[left(h, s)] and A[right(h, s)] are both max-heaps and
    # that A[h] violates the heap property i.e.
    # A[h] < A[left(h, s)] and/or A[h] < A[right(h, s)]
    aih = ai(h, s)
    largest = aih
    if 2*h <= s: # Look for the left child, if any
        l = left(h, s)
        ail = ai(l, s)
        if (A[aih] < A[ail]):
            largest = ail
    if 2*h+1 <= s: # Look for the right child, if any
        r = right(h, s)
        air = ai(r, s)
        if (A[largest] < A[air]):
            largest = air
    # A[largest] = max (A[aih], A[ail], A[air]) provided A[ail] and/or A[air] exist
    if largest <> aih:
        swap (A, aih, largest)
        heapify (A, hi(largest, s), s)

# The above function being tail-recursive we translate it into iteration

def heapifyIterative0 (A, h, s): # Heapify the array slice A[ai(1, s)..ai(s,s)]
    # Heap property: Forall j in {1,...,s}: A[Parent(j)] >= A[j] where
    # size (A) = s
    # Assuming that A[left(h, s)] and A[right(h, s)] are both max-heaps and
    # that A[h] violates the heap property i.e.
    # A[h] < A[left(h, s)] and/or A[h] < A[right(h, s)] 
    aih = ai(h, s)
    largest = aih
    if 2*h <= s: # Look for the left child, if any
        l = left(h, s)
        ail = ai(l, s)
        if (A[aih] < A[ail]):
            largest = ail
    if 2*h+1 <= s: # Look for the right child, if any
        r = right(h, s)
        air = ai(r, s)
        if (A[largest] < A[air]):
            largest = air
    # A[largest] = max (A[aih], A[ail], A[air]) provided A[ail] and/or A[air] exist
    while largest <> aih:
        swap  (A, aih, largest)
        h = hi(largest, s)
        aih = ai(h, s)
        largest = aih
        if 2*h <= s: # Look for the left child, if any
            l = left(h, s)
            ail = ai(l, s)
            if (A[aih] < A[ail]):
                largest = ail
        if 2*h+1 <= s: # Look for th eright child, if any
            r = right(h, s)
            air = ai(r, s)
            if (A[largest] < A[air]):
                largest = air

# The code above in heapifyIterative0 is simply too repetitious  and
# python does not have a repeat...until or do...until or do...while kind
# of loop so we use functional/procedural abstraction to reduce repetition.
# Further we need to make sure array index does not go out of bounds

def heapifyIterative1 (A, h, s): # Heapify the array slice A[ai(1, s)..ai(s,s)]
    # Heap property: Forall j in {1,...,s}: A[Parent(j)] >= A[j] where
    # size (A) = s
    # Assuming that A[left(h, s)] and A[right(h, s)] are both max-heaps and
    # that A[h] violates the heap property i.e.
    # A[h] < A[left(h, s)] and/or A[h] < A[right(h, s)]
    def largestindex (h, s):
        aindexh = ai(h, s)
        largestind = aindexh
        if 2*h <= s: # Look for the left child, if any
            l = left(h, s)
            ail = ai(l, s)
            if (A[aindexh] < A[ail]):
                largestind = ail
        if 2*h+1 <= s:
            r = right(h, s)
            air = ai(r, s)
            if (A[largestind] < A[air]):
                largestind = air
        return (largestind, aindexh)

    # heapifyIterative1 start
    (largest, aih) = largestindex (h, s)
#    aih = ai(h, s)
    # A[largest] = max (A[ail], A[air], A[aih])
    ## if largest <> aih:
    ##     swap (A, aih, largest)
    ##     heapify (A, hi(largest, s), s)
    while largest <> aih:
        swap  (A, aih, largest)
        h = hi(largest, s)
        (largest, aih) = largestindex (h, s)

# Further improvements are possible.
# 1. repeated computations of l and r can be simplified since
#    l = 2*h and r = l+1
# 2. right child cannot exist unless left child also exists. Hence if l>=s
#    r > s and does not exist, so the checking for right child can be in
#    the then clause of the check l <= s.

def heapifyIterative2 (A, h, s): # Heapify the array slice A[ai(1, s)..ai(s,s)]
    # Heap property: Forall j in {1,...,s}: A[Parent(j)] >= A[j] where
    # size (A) = s
    # Assuming that A[left(h, s)] and A[right(h, s)] are both max-heaps and
    # that A[h] violates the heap property i.e.
    # A[h] < A[left(h, s)] and/or A[h] < A[right(h, s)]
    def largestindex (h, s):
        aindexh = ai(h, s)
        largestind = aindexh
        l = 2*h
        r = l+1 # h < l < r always and l>=s implies r > s
        if l <= s: # Look for the left child, if any
            # l = left(h, s) # repetition
            ail = ai(l, s)
            if (A[aindexh] < A[ail]):
                largestind = ail
            if r <= s: # h < l < r
                # r = right(h, s) # repetition 
                air = ai(r, s)
                if (A[largestind] < A[air]):
                    largestind = air
        return (largestind, aindexh)

    # heapifyIterative1 start
    (largest, aih) = largestindex (h, s)
#    aih = ai(h, s)
    # A[largest] = max (A[ail], A[air], A[aih])
    ## if largest <> aih:
    ##     swap (A, aih, largest)
    ##     heapify (A, hi(largest, s), s)
    while largest <> aih:
        swap  (A, aih, largest)
        h = hi(largest, s)
        (largest, aih) = largestindex (h, s)

def heapify (A, h, s):
    ## heapifyTailRecursive (A, h, s)
    ## print 'heapifyTailRecursive (A, h, s)'
    ## heapifyIterative0 (A, h, s)
    ## print 'heapifyIterative0 (A, h, s)'
    ## heapifyIterative1 (A, h, s)
    ## print 'heapifyIterative1 (A, h, s)'
    heapifyIterative2 (A, h, s)
    print 'heapifyIterative2 (A, h, s)'
    
def buildHeap (A): # Heapify a given arbitrary array
    s = len (A)
    h = s//2
    while (h > 0):
        heapify (A, h, s)
        h -= 1

def heapSort (A): # Sorts the heap in non-descending order using max heap
    buildHeap (A)
    # The largest element is in A[1]
    s = len(A)
    h = s
    while h > 1:
        swap (A, 0, ai(h, s))
        s -= 1
        h -= 1
        heapify (A, 1, s)
        

# try it
B = [-12, -24, -12, 0, 123, 45, 1, 20, 0, -24]
print B
buildHeap (B)
print B
heapSort (B)
print B
S = ['Kajol', 'Madhuri', 'Aishwarya', 'Amisha', 'Urmila', 'Juhi', 'Raveena', 'Sonali']
print S
buildHeap (S)
print S
heapSort (S)
print S