Understanding heapsort algorithm
Heapsort is mostly used to sort arrays, but it can also be used to sort other list data structures. However, as it relies on the random access provided by arrays, heapsort may reduce the algorithm's efficiency. For the sake of this example, we will take an integer array and apply heapsort to it.
Algorithm
When applied to an array arr of size n, heapsort works in two main steps, as described below. (A max heap is a complete binary tree, stored here in arr using the standard index mapping where the children of index i are at 2*i + 1 and 2*i + 2, in which every parent is greater than or equal to its children.)
- Step 1: Build a max heap from the input array
- Step 2: Remove the top element and heapify again
Step 1: Build the heap
To build a max heap, the algorithm starts from the last non-leaf node (the deepest node that still has at least one child) and moves upward to the root. This is done by iterating i from n/2 - 1 (using integer division) down to 0 and calling heapify(arr, n, i) at each step.
n/2 - 1?In a binary heap stored as an array, all elements from index
n/2 to n-1 are leaf nodes. Leaf nodes already satisfy the heap property, so there is no need to heapify them. Starting from n/2 - 1, ensure that every internal node is heapified, resulting in a valid max-heap.After this phase, the largest element in the array is guaranteed to be at the root index (index 0).
Liking the course? Check our discounted plans to continue learning.