from array204 import Array

class MaxHeap :
  """ An array-based implementation of the max-heap."""

  def __init__( self, maxSize ):
    """Create a max-heap with maximum capacity of maxSize."""
    self._elements = Array( maxSize )
    self._count = 0
    
  def __len__( self ):
    """ Return the number of items in the heap."""
    return self._count

  def __str__( self ):
    """Return a string representation of the heap."""
    s = ''
    for i in range( len( self ) ):
      s += str( self._elements[i] ) + ', '
    return s

  def capacity( self ):
    """ Return the maximum capacity of the heap."""
    return len( self._elements )   
    
  def add( self, value ):    
    """ Add a new value to the heap."""
    assert self._count < self.capacity(), "Cannot add to a full heap."   
    # Add the new value to the end of the list.
    self._elements[ self._count ] = value 
    self._count += 1                       
    # Sift the new value up the tree.
    self._sift_up( self._count - 1 )
    
  def extract( self ):    
    """ Extract the maximum value from the heap."""
    assert self._count > 0, "Cannot extract from an empty heap."   
    # Save the root value and copy the last heap value to the root.
    value = self._elements[0]    
    self._count -= 1                                 
    self._elements[0] = self._elements[ self._count ]  
    # Sift the root value down the tree.
    self._sift_down( 0 )
    return value
    
  def _sift_up( self, ndx ):
    """Sift the value at the ndx element up the tree."""
    if ndx > 0 :
      parent = (ndx - 1) // 2
      if self._elements[ndx] > self._elements[parent] :  # swap elements
        self._elements[ndx], self._elements[parent] = \
        self._elements[parent], self._elements[ndx]
        self._sift_up( parent )
        
  def _sift_down( self, ndx ):
    """ Sift the value at the ndx element down the tree. """
    left = 2 * ndx + 1
    right = 2 * ndx + 2    
    # Determine which node contains the larger value, left or right.
    largest = ndx
    if left < self._count and self._elements[left] >= self._elements[largest]:
      largest = left
    if right < self._count and self._elements[right] >= self._elements[largest]:
      largest = right
    if largest != ndx:   # one of the children holds larger value
      self._elements[largest], self._elements[ndx] = \
          self._elements[ndx], self._elements[largest]
      self._sift_down( largest )