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.