# Heap.py
class Heap(object):

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

    def __init__(self, items=None):
    
        '''post: a heap is created with specified items, a list '''

        self.heap = [None]
        if items is None:
            self.heap_size = 0
        else:
            self.heap += items
            self.heap_size = len(items)
            self._build_heap()

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

    def size(self):

        '''post: returns number of items in the heap'''

        return self.heap_size
    
    #------------------------------------------------------------

    def _heapify(self, position):
    
        '''pre: items from 0 to position - 1 satisfy the heap property
        post: heap property is satisfied for the entire heap'''
        
        item = self.heap[position]
        while position * 2 <= self.heap_size: # if left child exists
            child = position * 2 #go to the left child
            # if right child exists and is larger than left child, go there
            if (child != self.heap_size and 
                self.heap[child+1] > self.heap[child]):
                child += 1
            if self.heap[child] > item: #if largest child item is > our item
                self.heap[position] = self.heap[child] #move child item up
                position = child #work from the new position
            else:
                break  
        self.heap[position] = item #place item in the correct position

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

    def delete_max(self):
    
        '''pre: heap property is satisfied
        post: maximum element in heap is removed and returned, heap property is restored.'''
	
        if self.heap_size > 0:
            max_item = self.heap[1]
            self.heap[1] = self.heap[self.heap_size] #place the last item at the root
            self.heap_size -= 1
            self.heap.pop()
            if self.heap_size > 0:
                self._heapify(1) #move the item at the root down to the correct position
            return max_item

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

    def insert(self, item):
    
        '''pre: heap property is satisfied
        post: item is inserted in proper location in heap'''
    
        self.heap_size += 1
        # extend the length of the list
        self.heap.append(None) #reserve a place for item
        position = self.heap_size
        parent = position // 2 
        while parent > 0 and self.heap[parent] < item: #parent exists and value is < our item
            # move item down
            self.heap[position] = self.heap[parent] #move parent item down
            position = parent    #Go up one position in the heap
            parent = position // 2
        # Position is now the correct spot.  Put item there.
        self.heap[position] = item

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

    def _build_heap(self):
    
        '''pre: self.heap has values in 1 to self.heap_size 
        post: heap property is satisfied for entire heap'''
        
        # 1 through self.heap_size
        for i in range(self.heap_size // 2, 0, -1): # stops at 1
            #Start with the node in the middle, the last one with a child.  It's the parent of the last node.
            #The last half of the items satisifies the heap property, since every item there has no children.
            self._heapify(i)

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

    def heapsort(self):
    	
        '''pre: heap property is satisfied
        post: items are sorted in self.heap[1:self.sorted_size]'''
    
        sorted_size = self.heap_size
        for i in range(0, sorted_size - 1):
            # Since delete_max calls pop to remove an item, we need 
            # to append a dummy value to avoid an illegal index.
            self.heap.append(None)
            item = self.delete_max()
            self.heap[sorted_size - i] = item