Sorting Algorithms: Heap Sort

Learn about heap data structure and how it is used for sorting

Introduction

Heap is a data structure that represents an array in a binary tree-based format. Heap imposes the following rules for its structure:

• Completeness. Every level of the heap is completely filled with elements. However, the last level may be partially filled with elements starting from the left.
• Heap rule. The value of any parent’s node must be less or equal to the values of its children. If this property is satisfied, the heap is called min-heap. There also exists a max-heap variation for which parents’ values must be greater than children’s values.

Examples and code in this article will be provided for min heaps. The algorithm workflow for max heaps looks very similar. An example of a min-heap is shown below.

Heap is usually stored in the form of an array. If a parent has an index i, then the positions of its left and right children are 2 * i + 1 and 2 * i + 2 respectively. Inversely, if a non-root node has an index i, then its parent’s node has an index (i - 1) // 2. Following…