Template

"""
Name - Binary Min-Heap and Sort
"""
class BinaryMinHeap:
    # DO NOT MODIFY THIS CLASS #
    def __init__(self):
        """
        Creates an empty hash table with a fixed capacity
        """
        self.table = []
    def __eq__(self, other):
        """
        Equality comparison for heaps
        :param other: Heap being compared to
        :return: True if equal, False if not equal
        """
        if len(self.table) != len(other.table):
            return False
        for i in range(len(self.table)):
            if self.table[i] != other.table[i]:
                return False
        return True
    def get_size(self):
        """
        Returns the size of heap
        :return: returns the total number of elements in min heap
        """
        return len(self.table)
    def parent(self, position):
        """
        Returns the parent of current position
        :param position: Position of which the parent is required
        :return: returns the position of parent in min heap
        """
        if position == 1 or position == 2:
            return 0
        
        # if pos is an odd number, then it's a left child
        # if it's even, then it's a right child.
        if position % 2 == 0:
            return (position - 2) // 2
        else:
            return (position - 1) // 2
    def left_child(self, position):
        """
        Return the left child of current position
        :param position: Position of which the left child is required
        :return: returns the position of left child in min heap
        """
        left_child = (position + 1)*2 - 1
        left_child = int(left_child)
        if left_child < len(self.table):
            return left_child
        else:
            return None
    def right_child(self, position):
        """
        Return the right child of current position
        :param position: Position of which the parent is required
        :return: returns the position of right child in min heap
        """
        right_child = (position + 1) * 2
        right_child = int(right_child)
        if right_child < len(self.table):
            return right_child
        else:
            return None
    def has_left(self, position):
        """
        Return True if the current position has left child
        :param position: Position of which the left child is required
        :return: Return True if the current position has left child
        """
        if self.left_child(position) is None:
            return False
        return True
    def has_right(self, position):
        """
        Return True if the current position has right child
        :param position: Position of which the right child is required
        :return: Return True if the current position has right child
        """
        if self.right_child(position) is None:
            return False
        return True
    def find(self, value):
        """
        Return the index of value location
        :param value: value location to find
        :return: Return the index of value location
        """
        try:
            return self.table.index(value)
        except ValueError:
            return None
    def heap_push(self, value):
        """
        Push the value in the min heap and also maintains
        the property of min heap
        :param value: value to be inserted
        """
        if self.find(value) is None:
            self.table = self.table + [value]
            self.percolate_up(self.get_size() - 1)
    def heap_pop(self, value):
        """
        Removes the value in min heap and also maintains
        the property of min heap
        :param value: value to be deleted
        :return: returns None if the value is not found
        """
        index = self.find(value)
        if index is not None:
            self.table[index] = self.table[self.get_size() - 1]
            self.table.pop()
        else:
            return None
        if self.get_size() > 0:  # more than one element in the heap
            self.percolate_down(index)
        else:
            return None
    def pop_min(self):
        """
        Removes the minimum value in min heap and also maintains
        the property of min heap
        :return: returns None if the min heap is empty
        """
        if self.get_size() <= 0:
            return None
        root_value = self.table[0]
        self.table[0] = self.table[self.get_size() - 1]
        self.table.pop()
        if self.get_size() > 0:  # more than one element in the heap
            self.percolate_down(0)
        return root_value
    def swap(self, p1, p2):
        """
        Swap values between p1 and p2
        :param p1: first value to be swapped with second value
        :param p2: second value to be swapped with first value
        """
        a_val = self.table[p1]
        b_val = self.table[p2]
        self.table[p1] = b_val
        self.table[p2] = a_val
    def percolate_up(self, position):
        """
        Bubble up the current postion value to maintain
        the peoperty of min heap
        :param position: position at which the bubble up is required
        """
        if position == 0:
            return
        parent = self.parent(position)
        if self.table[position] < self.table[parent]:
            self.swap(position, parent)
            self.percolate_up(parent)
    def get_children_of(self, position):
        """
        Return the positions of all children of current position
        :param position: position at which the children is to find
        :return: Return the positions of all children of current position
        """
        index = len(self.table)
        if index <= (2*position + 1):
            return []
        elif index == (2*position + 2):
            return [2*position + 1]
        else:
            return [2*position + 1, 2*position + 2]
    def percolate_down(self, position):
        """
        Bubble down the current postion value to maintain
        the property of min heap
        :param position: position at which the bubble down is required
        """
        children = self.get_children_of(position)
        
        # Three cases: leaf, one child, two children
        if children is []:
            return
        elif len(children) == 1:
            if self.table[children[0]] < self.table[position]:
                self.swap(children[0], position)
                self.percolate_down(children[0])
        else:  # len(children) == 2
            left = self.table[children[0]]
            right = self.table[children[1]]
            root = self.table[position]
            
            if left < root or right < root:
                if left < right:
                    self.swap(children[0], position)
                    self.percolate_down(children[0])
                else:
                    self.swap(children[1], position)
                    self.percolate_down(children[1])
def heap_sort(unsorted):
    """
    Converts an unsorted list into a sorted list using min heap
    :param unsorted: An unsorted list
    :return: returns sorted list
    """
    arr = []
    heap = BinaryMinHeap()
    # Build a min heap.
    for i in range(len(unsorted)):
        heap.heap_push(unsorted[i])
    # One by one extract elements
    for i in range(heap.get_size()):
        arr.append(heap.pop_min())
    return arr
# Driver code to run above program
if __name__ == '__main__':
    heap = BinaryMinHeap()  # Creating object of Min-Heap
    # Inserting elements from 1-5 in heap 
    heap.heap_push(1)
    heap.heap_push(2)
    heap.heap_push(3)
    heap.heap_push(4)
    heap.heap_push(5)
    # Calling functions
    assert(heap.find(3) == 2)
    assert(heap.table[heap.find(3)] == 3)