Heap Sort in Python
Introduction
Heap Sort is another example of an efficient sorting algorithm. Its main advantage is that it has a great worst-case runtime of O(n*logn) regardless of the input data.
As the name suggests, Heap Sort relies heavily on the heap data structure – a common implementation of a Priority Queue.
Without a doubt, Heap Sort is one of the simplest sorting algorithms to implement and coupled with the fact that it’s a fairly efficient algorithm compared to other simple implementations, it’s a common one to encounter.
Heap Sort
Heap Sort works by “removing” elements from the heap part of the array one-by-one and adding them to the sorted part of the array. Before we get further into the explanation and revisit the heap data structure, we should mention a few attributes of Heap Sort itself.
It is an in-place algorithm, meaning that it requires a constant amount of additional memory, i.e. the memory needed doesn’t depend on the size of the initial array itself, other than the memory needed to store that array.
For example, no copies of the original array are necessary, and there is no recursion and recursive call stacks. The simplest implementation of Heap