Heap sort is one of traditional sorting algorithms with time complexity $\mathcal{O}(n\ln n)$. After reading this article, you will be able to build a left-justified binary tree and implement heap sorting algorithm. We first defined some terms that will be used later. Definition (Balanced tree) A binary tree of depth $n$ is balanced if all the nodes at depth $0$ through $n-2$ have two children. That is, for any two leaves in the tree the difference is at most 1. We can see some examples for balanced trees and imbalanced trees. Definition (Left-justified binary tree) A binary tree is left-justified if all the leaves are at the same depth and all the leaves at depth $n+1$ are to the left of all nodes at depth $n$. The following figures illustrates the left justified tree: In order to implement heap sorting algorithm, we should first build a binary max-heap (min-heap) tree which is a left-justified balanced tree and whose pa...