# Heap Sort and Binary Tree Sort Algorithms (Python)

### Heap Sort

A Binary Heap is a Complete Binary Tree where the items are stored in a special order such that the value in a parent node is greater or smaller than the two values in the children nodes.

Heap Sort is a comparison-based sorting algorithm — somewhat similar to selection sort — which divides a list into sorted and unsorted parts, then it iteratively shrinks the unsorted part by extracting the largest value and moving that to the sorted part. The improvement consists of the usage of a heap data structure rather than a linear-time search to find the maximum.

### Binary Tree Sort

A Binary Tree Sort is an algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.

Average Case Time Complexity : $$\O(N\: log N)\$$ adding one element to a Binary Search Tree on average takes $$\O(log N)\$$ time (height of a tree). Therefore, adding $$\n\$$ elements will take $$\O(N\: log N)\$$ time.

Worst Case Time Complexity : $$\O(N^2)\$$. The worst case can be improved by using a self-balancing binary search tree, which will take $$\O(N\: log N)\$$ time to sort the array in worst case.

Just for practicing OOP, I've implemented the above algorithms, and if you'd like to review the code and provide any change/improvement recommendations (especially I'm not still sure how to design exception handler for each class), please do so, and I appreciate that.

## ideone.com Demo (Python)

### Code

'''
This module combines Tree Sorting Algorithms, just for practicing OOP in Python.
It is an imaginary problem to solve assuming that we should use OOP to write these algorithms, even if that'd be unnecessary.
Currently it has a __super__ class TreeSortingAlgorithms
with two internal HeapSort and BinarySort classes, each with their own internal classes.
I'm not sure how to design an OOP exception handling for each class or for the entire module.

'''
# imports random for testing the algorithms
import random
# imports TypeVar and List typings for type hinting
from typing import List, TypeVar

# Instantiates the TypeVar
T = TypeVar('T')

class TreeSortingAlgorithms:
'''This super class has two subclasses of HeapSort and BinarySort.'''
class HeapSort:
'''HeapSort gets an input list, uses iterative or recursive bottom-up approaches
and sorts the input list.
'''
class ExceptionHandling(Exception):
'''This class is supposed to handle the exceptions for Heap Sort, not yet though'''
pass

def heap_sort(input_list: List[T], input_size: int) -> None:
'''
Sorts a numerical list in an ascending order
e.g., [None, 5, 3.1, 2, 9] to [None, 2, 3.1, 5, 9]
Input list is a list which has a None first element at index 0
The zero index is just set to None for simplicity.
'''
TreeSortingAlgorithms.HeapSort.buttom_up_heap_sort(
input_list, input_size)

while input_size > 1:
# Assigns the max value of the heap
max_value = input_list[1]
# Swaps the max value with the last element value
input_list[1], input_list[input_size] = input_list[input_size], max_value
# Increments
input_size -= 1
# Restores down the first element
TreeSortingAlgorithms.HeapSort.restore_down(
1, input_list, input_size)

def buttom_up_heap_sort(input_list: List[T], input_size: int) -> None:
'''
Builds the heap sort using bottom up approach
'''
heap_index = input_size // 2

while heap_index >= 1:
# Restores down the element
TreeSortingAlgorithms.HeapSort.restore_down(
heap_index, input_list, input_size)
# Increments
heap_index -= 1

def restore_down(heap_index: int, input_list: List[T], input_size: int) -> None:
'''
Restores down the element
'''
# Assigns the item value
heap_value = input_list[heap_index]
# Assigns the left and right child indices
left_child_index, right_child_index = 2 * heap_index, 2 * heap_index + 1

while right_child_index <= input_size:
if heap_value >= input_list[right_child_index] and heap_value >= input_list[left_child_index]:
input_list[heap_index] = heap_value
return
elif input_list[left_child_index] > input_list[right_child_index]:
input_list[heap_index], heap_index = input_list[left_child_index], left_child_index
else:
input_list[heap_index], heap_index = input_list[right_child_index], right_child_index

# Assigns the left and right child indices
left_child_index, right_child_index = 2 * heap_index, 2 * heap_index + 1

if left_child_index == input_size and heap_value < input_list[left_child_index]:
input_list[heap_index], heap_index = input_list[left_child_index], left_child_index
input_list[heap_index] = heap_value

class BinarySort:
'''Binary Sort class has a class of Node, an ExceptionHandling class (to be written),
and the following methods:
is_empty: returns boolean if the tree is empty
recursive_insert: recursively insert the new values in the tree
iterative_insert: iteratively insert the new values in the tree'''

def __init__(self) -> None:
'''
Initializes the Root Node of the Binary Tree to None;
'''
self.root: BinarySort = None

class ExceptionHandling(Exception):
'''This class is supposed to handle the exceptions for Binary Sort, not yet though'''
pass

class Node:
'''This class instantiate the Node'''

def __init__(self, node_value: float) -> None:
'''
Initializes a node with three attributes;
node_value (Node Value): Must be an float;
right_child (Right Child): Initializes to None; Its value must be larger than the Root Node;
left_child (Left Child): Initializes to None; Its value must be smaller than the Root Node;
'''
self.node_value: Node = node_value
self.right_child: Node = None
self.left_child: Node = None

def is_empty(self) -> bool:
'''
Returns True if the tree doesn't have a node;
'''
return self.root is None

def recursive_insert(self, new_value: float) -> None:
'''
Recursively inserts an float-value Node in the Tree;
'''
self.root = self._recursive_insert(self.root, new_value)

def _recursive_insert(self, parent_node: Node, new_value: float) -> Node:
'''
Inserts an float value in the left or right Node;
Returns the parent Node;
'''

# If the parent node is none
if parent_node is None:
parent_node = TreeSortingAlgorithms.BinarySort.Node(new_value)
# If the new Node value is smaller than its parent Node value
elif new_value < parent_node.node_value:
parent_node.left_child = self._recursive_insert(
parent_node.left_child, new_value)
# If the new Node value is bigger than its parent Node value
else:
parent_node.right_child = self._recursive_insert(
parent_node.right_child, new_value)

return parent_node

def iterative_insert(self, new_value: float) -> None:
'''Iteratively inserts a new value as a Node in the Binary Search Tree'''
new_node = TreeSortingAlgorithms.BinarySort.Node(new_value)

# If tree is not empty
if TreeSortingAlgorithms.BinarySort().is_empty():
# Assigns the parent node to the Root
parent_node = self.root
while True:
# If the new value is smaller than the parent node value
if new_value < parent_node.node_value:
# If parent node has a left child
if parent_node.left_child:
parent_node = parent_node.left_child
# If parent node doesn't have a left child
else:
parent_node.left_child = new_node
break
# If the new value is not smaller than the parent node value
else:
# If parent node has a right child
if parent_node.right_child:
parent_node = parent_node.right_child
else:
# If parent node doesn't have a right child
parent_node.right_child = new_node
break
return
self.root = new_node

def __iter__(self) -> None:
'''
Calls the _inorder traversing method recursively;
'''
self._inorder(self.root)

def _inorder(self, parent_node: Node) -> None:
'''
Traverses the tree inorder (Left Node, Root Node, Right Node)
'''
if parent_node is None:
return
# Recurse the left node
self._inorder(parent_node.left_child)
# Prints the parent node
print(parent_node.node_value)
# Recurse the right node
self._inorder(parent_node.right_child)

if __name__ == '__main__':
# -------------------------------------------------------------------------
# ---------------------------- Binary Sort Tests ---------------------------
# -------------------------------------------------------------------------
tree = TreeSortingAlgorithms.BinarySort()
delimiter = '-' * 50
# -------------------------- Recursive Test --------------------------

print('Recursive Binary Search Tree outputs: ')
for i in range(random.randint(20, 30)):
tree.recursive_insert(random.uniform(-10, 10))
tree.__iter__()

# -------------------------- Iterative Test --------------------------

print('Iterative Binary Search Tree outputs: ')
for i in range(random.randint(20, 30)):
tree.iterative_insert(random.uniform(-10, 10))

tree.__iter__()

# -------------------------------------------------------------------------
# ---------------------------- Heap Sort Tests ---------------------------
# -------------------------------------------------------------------------
# Tests the heap sort with some randomly generated lists
for test_heap_index in range(10):
# Generates random input list size for testing
input_size = random.randint(20, 50)
# Assigns the first element of the input list to None
input_list = [None]
# Randomly generates the other elements of the input list
# Also, assigns that to a second test list for comparison
test_list = input_list[1:] = [random.randint(100, 1000)
for _ in range(1, input_size + 1)]
# Sorts the input list
TreeSortingAlgorithms.HeapSort.heap_sort(input_list, input_size)
# If heap sort list output is equal to Python built-in sort output
if (sorted(test_list) == input_list[1:]):
print(f'🍏 Heap Sort Test {test_heap_index + 1} was successful!')
# Otherwise if the input list is not sorted
else:
print(f'🍎 Heap Sort Test {test_heap_index + 1} was not successful!')


### Sources

The Binary Tree Sort section of this question has been also previously reviewed in the first following link:

## Modules instead of "namespace" classes

TreeSortingAlgorithms has no right to exist. It's good to want to put stuff in namespaces, but your nested classes are confusing and difficult-to-read. Instead, just put your algorithmic classes into a different file and use it as a module. That will get you a namespace but also be more legible, easier to deal with in source control, etc.

Also, be careful:

This super class has two subclasses of HeapSort and BinarySort.

Most people would interpret that as HeapSort being a child or derivation of TreeSortingAlgorithms, which is not the case. This is not a superclass/subclass relationship, but rather a nested class relationship.

## Terminology

            # Increments
heap_index -= 1


That's not an increment, it's a decrement.

## Loop like a native

        while heap_index >= 1:
# Restores down the element
TreeSortingAlgorithms.HeapSort.restore_down(
heap_index, input_list, input_size)
# Increments
heap_index -= 1


should be something like

starting_index = heap_index
for heap_index in range(starting_index, 0, -1):
# ...


# Assigns the left and right child indices


This is worse than not having a comment at all. If you're near-verbatim rewriting Python into English, it's time to delete the comment or write something useful, e.g.

# The left index starts at double the heap index because (algorithmic explanation)


## English is not C

This isn't my first review of your code, and you need to change this (again). Stop writing semicolons at the end of your comments.

## Real tests

It's great that you've written some test code. To make it useful, you should add some asserts that test the output of your code against known expected outputs.

## Unicode symbols

Your apples are hilarious. Keep them, but I think that they may present problems if ever you have team-shared code across a wide variety of platforms and editors. Consider something like this instead:

GREEN_APPLE = '\U0001F34F'

# ...

print(f'{GREEN_APPLE} Heap Sort Test {test_heap_index + 1} was successful!')


## Iterators

This is wrong:

class BinarySort:

def __iter__(self) -> None:
'''
Calls the _inorder traversing method recursively;
'''
self._inorder(self.root)

def _inorder(self, parent_node: Node) -> None:
...


In this answer, I suggested instead of creating a function for printing the tree in order, you create an iterator that could return the values in the tree in order, which the caller could print. I mentioned __iter__(self) and __next__(self) methods, with the hope/intention that you would do some research yourself into how to create iterators.

I suppose I could have provided an example:

class Container:

def __init__(self, *data):
self._items = data

def __iter__(self):
return Container.Iterator(self)

class Iterator:
def __init__(self, container):
self._container = container
self._i = 0

def __next__(self):
if self._i < len(self._container._items):
item = self._container._items[self._i]
self._i += 1
return item
raise StopIteration


Here, I have a Container. It stores a sequence of items.

>>> stuff = Container(1, 2, 3, 5, 8, 13)


While it defines an __iter__ method, you should never call that method yourself. Instead, you should use the iter() function:

>>> it = iter(stuff)
>>> type(it)
<class '__main__.Container.Iterator'>


Note that the __iter__ method does return something. It must return an iterator, which is something that implements the __next__ method. Our Container.Iterator object does do that. Again, you never call the __next__ method yourself; you call the next() function instead:

>>> next(it)
1
>>> next(it)
2
>>> next(it)
3
>>> next(it), next(it), next(it)
(5, 8, 13)
>>> next(it)
Traceback (most recent call last):
File "<pyshell#40>", line 1, in <module>
next(it)
File "C:\Users\aneufeld\Desktop\Playground\Python\StackOverflow\iter.py", line 19, in __next__
raise StopIteration
StopIteration


Notice how that iter(stuff) returned an iterator, and calling next(iterator) returned each item from our container in sequence.

Normally, you would use the iterator in a loop, breaking out when StopIteration is raised:

>>> it = iter(stuff)
>>> while True:
try:
val = next(it)
print(val)
except StopIteration:
break

1
2
3
5
8
13
>>>


But Python will call it = iter() and val = next(it), and catch the StopIteration exception for you, if you write it like this:

>>> for val in stuff:
print(val)

1
2
3
5
8
13
>>>


## Tree Iterator

A Tree iterator would be slightly more complicated. The iterator itself would need a stack (list) to keep track of which node it is at. While a node has a left child, you'd travel down to those children, pushing the current node onto your stack. When no left child exist, you'd return the node's value. When a right child exists, you'd travel down to those children, but not pushing the current node onto the stack. When no children exists, you'd pop the last node you pushed off of your stack, return its value, and visit its right child node. Effectively, you are traversing the tree inorder, but instead of using recursive calls, you have to keep track of where you are, and which direction you are going.

Left to student.