__license__ = 'Nathalie (c) EPITA'
__docformat__ = 'reStructuredText'
__revision__ = '$Id: heap.py 2019-03-07'

"""
Heap homework
2019
@author: login
"""

#given function

def Heap():
  """ returns a fresh new empty heap
       :rtype: list (heap)
  """
  return [None]

#---------------------------------------------------------------

def is_empty(H):
  """ tests if H is empty
        :param H: the heap
        :rtype: bool
  """
  return len(H) < 2

def push(H, elt, val):
  """ adds the pair (val, elt) to heap H (in place)

       :param H: The heap
       :param elt: The element to add
       :param val: The value associated to elt
  """
  i = len(H)
  H.append((val,elt))

  while( i != 0 and i//2 != 0 and H[i][0] < H[i//2][0]):
    H[i] = H[i//2]
    H[i//2] = (val, elt)
    i = i//2

def __heapify(L,i):
  """
    outputs a heap containing the elements of a given list in the correct minHeap order
    :param L: the given list
    :param i: the index of the root

    :rtype: Heap
  """
  if(2*i < len(L) and L[i][0] > L[2*i][0]):
    temp = L[i]
    L[i] = L[2*i]
    L[2*i] = temp

    __heapify(L, 2*i)

  if(2*i+1 < len(L) and L[i][0] > L[2*i+1][0]):
    temp = L[i]
    L[i] = L[2*i+1]
    L[2*i+1] = temp

    __heapify(L, 2*i+1)

def pop(H):
    """ removes and returns the pair of smallest value in the heap H

       :param H: The heap
       :rtype: (num, any) (the removed pair)
    """
    if(len(H) > 2):
      output = H[1]
      H[1] = H.pop()

      __heapify(H,1)

      return output
    else:
      return H.pop()
#---------------------------------------------------------------
def __isInMinHeapOrder(T,i):
  #I hope the name is explicit enough
  output = True

  if(2*i < len(T)):
    if (T[i] < T[2*i]):
      output = __isInMinHeapOrder(T,2*i)
    else:
      return False

  if(output and 2*i+1 < len(T)):
    if (T[i] < T[2*i+1]):
      output = __isInMinHeapOrder(T,2*i+1)
    else:
      return False

  return output

def is_heap(T):
    """ tests whether the complete tree T is a heap

       :param T: a complete tree in hierarchical representation
       :rtype: bool
    """
    return __isInMinHeapOrder(T,1)

def heap_sort(L):
    """ sorts the associative list L in increasing order according to values

        :param L: a list containing pairs (element, value)
        :rtype: (any, num) list (the list sorted)
    """
    H = Heap()
    for pair in L:
      push(H, pair[1], pair[0])

    output = []
    while len(H) > 1:
      output.append(pop(H))

    return output