California Polytechnic State University, San Luis Obispo

A heap is a tree in which items are sorted in a special way. There are two types of heaps: a min-heap and a max heap. A min-heap is one where the parent value is less than the value of the children. A max heap is one where the parent value is greater than the value of the children.

A heap sort algorithm for sorting in increasing order is as follows:
1) Build a max heap from input data
2) Replace the largest item (root) with the last item of the heap and reduce the size of the heap by 1. Then heapify the root of the tree.
3) Repeat step 2 while the size of the heap is greater than 1.

Learn Before

Related