Heap Sort and Binary Tree Sort Algorithms (Python)

Question

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:

• Binary Tree Sort Algorithm (Python) - Code Review

• Heap Sort - Geeks for Geeks

• Heap Sort - Wiki

• Tree Sort - Wiki

• Tree Sort - Geeks for Geeks

Answer 1

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):
   # ...

Useful comments

# 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!')

Answer 2

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.