"""
Created by Hadron DaVinci
https://hadrondavinci.com

For Educational Purposes
To Run:
    1) Download https://hadrondavinci.com/assets/code/2021-05-27/method1.py
    2) python method1.py

Code:
    -builds tree from breadth-first order
    -does heapify from leaves to root via reverse breadth-first traversal


Expected Output:
    Before Max Heaped
        ____-3___
       /         \
      11         _52
     /  \       /   \
   _4    23    70    65
  /
100

[-3, 11, 52, 4, 23, 70, 65, 100]

After Max Heaped
       ____100___
      /          \
    _23          _70
   /   \        /   \
  11    -3     52    65
 /
4
"""
# pip install binarytree
from binarytree import Node
from collections import deque


class BinaryTree:
    def __init__(self, node_list):
        self.root = self.get_node(node_list, index=0)

    def get_node(self, arr: list, index: int) -> Node:
        """
            Assumes data is in bread-first order
            Gets node and its children

            Given a node is at index i,
                its left child is at 2i + 1,
                its right child is at 2i + 2
                its parent is at floor((i - 1) / 2).
        """
        try:
            value = arr[index]
        except IndexError:
            return None

        node = Node(value)
        left_index = 2*index + 1
        right_index = 2*index + 2
        node.left = self.get_node(arr, left_index)
        node.right = self.get_node(arr, right_index)
        return node

    @staticmethod
    def largest_child(node):
        """
        Returns the largest child
        """
        if node.left and not node.right:
            # node left exists but not right
            return node.left

        elif node.right and not node.left:
            # node right exists but not left
            return node.right

        elif not node.left and not node.right:
            # this is a leaf b/c no child exists
            return None

        elif node.left.value and node.right.value:
            if node.left.value >= node.right.value:
                return node.left
            else:
                return node.right

    def heapify_node(self, node):
        """
        Used for maintaining a heap.
        Assumes nodes below are heapified

        Code swaps current node value with child value that:
            a) is largest amongst the children
            b) larger than current value
        """
        largest_child = self.largest_child(node)
        if not largest_child:
            return

        if not largest_child.value > node.value:
            return

        # swap parent value with child value
        node.value, largest_child.value = largest_child.value, node.value

        # reheapify child node since it was updated
        self.heapify_node(largest_child)

    def build_heap(self):
        for node in self.root.levelorder[::-1]:
            self.heapify_node(node)

    def get_last_node(self):
        """
        Returns the last node in tree.
        Internally, this library uses an array to keep track
        of the child nodes
        """
        number_of_nodes = self.root.size
        return self.root[number_of_nodes - 1]

    def delete_last_node(self):
        """
        Removes the last node in tree
        """
        number_of_nodes = self.root.size
        del self.root[number_of_nodes - 1]


def heap_sort(breadth_first_order):
    sorted_array = deque()
    h = BinaryTree(breadth_first_order)
    h.build_heap()
    while True:
        sorted_array.appendleft(h.root.value)

        # swap value at last and root node
        last_node = h.get_last_node()
        h.root.value, last_node.value = last_node.value, h.root.value

        # exit once only one node is in tree
        if h.root.size == 1:
            break

        # delete last node
        h.delete_last_node()

        # heapify root
        h.heapify_node(h.root)

    return list(sorted_array)


# Try Code
if __name__ == "__main__":
    array = [-3, 11, 52, 4, 23, 70, 65, 100]
    result = heap_sort(array)
    print(result)