Objective of these series of experiments is to understand Heap Sort. Heap Sort is a Sorting Algorithm which sorts a list of numbers using a Max Heap. Each experiment will introduce you to a new concept on top of all previously learned concepts. Before we start, we will review some key concepts which are essential to understand Heap Sort.
A complete binary tree(CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
A complete binary tree can be represented as an list. If parent node is at index i, left child node will be at index 2*i+1 and right child node will be at index 2*i+2.
A Binary heap is a CBT such that value in parent node are greater(smaller) than values in the child node. If it's greater than it is called Max heap and if it's smaller than it is called Min heap. In a Max-heap the root node or 0th index is largest among all elements.
Since a list of numbers can be represented as a Complete Binary Tree, first seven experiments deal with converting a CBT into a Max Heap. In last two experiments, you will learn about how to sort a list of numbers using the Max Heap.