#!/usr/bin/env python3
"""
binary_heap_tester.py
This demonstration uses a list to build and maintain a minHeap tree.
@author Richard White
@version 2017-04-24
"""

class BinaryHeap():
    """The BinaryHeap class implements the Binary Heap Abstract 
    Data Type as a list of values, where the index p of a parent
    can be calculated from the index c of a child as c // 2.
    """
    def __init__(self):
        self.heapList = [0]  # not used. Here just to make parent-
                             # child calculations work nicely.
        # Note that current size of heap = len(self.heapList) - 1

    def insert(self,value):
        """Inserts a value into the heap by:
        a. adding it to the end of the list, and then
        b. "percolating" it up to an appropriate position
        """
        self.heapList.append(value)     # value at end of list
        self.percolateUp(self.size())   # begins the percolation
                                        # process so the array
                                        # can retain its heap property

    def percolateUp(self, i):
        """Beginning at i, check to see if parent above is greater than
        value at i. If so, percolate i upwards to parent's position.
        """
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[i // 2]
                self.heapList[i // 2] = tmp
                # Could also use Python's swap syntax a,b = b,a
            i = i // 2                  # Ascend to parent and see if
                                        # we need to keep going
        

    def delMin(self):
        """This is a bit trickier. It's easy to return the minimum item,
        the first item on the list, but how do we readjust the heap then?
        """
        result = self.heapList[1]
        '''First, let's put another value up at the root of the heap. We'll
        just take the last one in our heap.
        '''
        self.heapList[1] = self.heapList.pop()
        '''This was one of the higher values in the heap, definitely not
        our minimum, so we need to percolate *down* the heap now.
        '''
        self.percolateDown(1)           # take value and move it 
                                        # down to its correct position
        return result

    def percolateDown(self,i):
        """Moves the item at i down to a correct level in the heap
        """
        while i * 2 <= self.size():      # while there are children...
            # Identify which child is lower
            if i * 2 + 1 > self.size():
                min_child = i * 2
            elif self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                min_child = i * 2
            else:
                min_child = i * 2 + 1
            # Now check to see if we need to move i down
            if self.heapList[i] > self.heapList[min_child]:
                tmp = self.heapList[min_child]
                self.heapList[min_child] = self.heapList[i]
                self.heapList[i] = tmp
            i = min_child

    def findMin(self):
        """Returns the minimum item in the heap, without removing it.
        """
        return self.heapList[1]

    def isEmpty(self):
        return len(self.heapList) - 1 == 0

    def size(self):
        return len(self.heapList) - 1

    def buildHeap(self, list_of_keys):
        """Code from textbook
        """
        i = len(list_of_keys) // 2
        self.heapList = [0] + list_of_keys[:]   # copies the list
        while (i > 0):
            self.percolateDown(i)
            i = i - 1

    def __repr__(self):
        return "BinaryHeap" + str(self.heapList)

def main():
    print("Demonstrating minHeap binary tree")
    bh = BinaryHeap()
    bh.insert(5)
    print(bh)
    bh.insert(7)
    bh.insert(3)
    bh.insert(11)
    bh.insert(1)
    bh.insert(50)
    bh.insert(15)
    print(bh)
    print(bh.findMin())
    print(bh.delMin())
    print(bh)

if __name__ == "__main__":
    main()