ITU324-Data Structures and Algorithms Laboratory
Practical No-9
AIM:- Implement HeapSort algorithm to sort an integer array in an ascending
and try to make it faster as much as possible
THEORY:-
Heap
Heap is a special tree-based data structure. A binary tree is said to follow a heap data structure if
It is a complete binary tree
All nodes in the tree follow the property that they are greater than their children
i.e. the largest element is at the root and both its children smaller than the root and so on. Such a
heap is called a max-heap. If instead, all nodes are smaller than their children, it is called a min-
heap
The following example diagram shows Max-Heap and Min-Heap.
Heap sort is one of the comparison based sorting algorithms used to arrange a list of elements in
order. Heapsort algorithm uses one of the tree concepts called Heap Tree. In this sorting
algorithm, we use Max Heap to arrange list of elements in Descending order and Min Heap to
arrange list elements in Ascending order.
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
How Heap Sort Works?
1. Since the tree satisfies Max-Heap property, then the largest item is stored at the root node.
2. Swap: Remove the root element and put at the end of the array (nth position) Put the last item of
the tree (heap) at the vacant place.
3. Remove: Reduce the size of the heap by 1.
4. Heapify: Heapify the root element again so that we have the highest element at root.
5. The process is repeated until all the items of the list are sorted.
Properties:
Not stable
In-place
O(n log n) comparisons and swaps
Not online
Not really adaptive
Step by Step Process
The Heap sort algorithm to arrange a list of elements in ascending order is performed using
following steps...
Step 1 - Construct a Binary Tree with given list of Elements.
Step 2 - Transform the Binary Tree into Max Heap.
Step 3 - Delete the root element from Max Heap using Heapify method.
Step 4 - Put the deleted element into the Sorted list.
Step 5 - Repeat the same until Max Heap becomes empty.
Step 6 - Display the sorted list.
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Example:
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Complexity of the Heap Sort Algorithm
To sort an unsorted list with 'n' number of elements, following are the complexities...
Worst Case : O(n log n)
Best Case : O(n log n)
Average Case : O(n log n)
Source Code:-
from drawtree import draw_level_order
# Function to heapify a subtree rooted at index i
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child
# Check if left child is larger than root
if l < n and arr[l] > arr[largest]:
largest = l
# Check if right child is larger than largest so far
if r < n and arr[r] > arr[largest]:
largest = r
# If largest is not root, swap and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
print("After Heapify:")
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
draw_level_order(arr)
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
print("Initial binary tree:")
draw_level_order(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
print("After extracting max element:")
draw_level_order(arr)
heapify(arr, i, 0)
arr = list(map(int, input("Enter the array elements separated by spaces: ").split()))
heapSort(arr)
print("Sorted array is:", arr)Output:-
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Viva Questions:-
What is the time complexity of Build Heap operation. Build Heap is used to build a
max(or min) binary heap from a given array. Build Heap is used in Heap Sort as a first
step for sorting.
(A) O(nLogn) (B) O(n^2) (C) O(Logn) (D) O(n)
Ans:- Option (A) O(nLog n)
Suppose we are sorting an array of eight integers using heapsort, and we have just finished
some heapify (either maxheapify or minheapify) operations. The array now looks like this:
16 14 15 10 12 27 28
How many heapify operations have been performed on root of heap?
(A) 1 (B) 2 (C) 3 or 4 (D) 5 or 6
Ans:- Option (B) 2
Explanation:- In Heapsort, we first build a heap, then we do following operations till the
heap size becomes 1.
a) Swap the root with last element
b) Call heapify for root
c) reduce the heap size by 1.
In this question, it is given that heapify has been called few times and we see that last two
elements in given array are the 2 maximum elements in array. So situation is clear, it is
maxheapify which has been called 2 times.
Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max
heap found in the above question, Which one of the following is the sequence of items in
the array representing the resultant heap?
(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4 (B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3 (D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Ans:- Option (A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Consider a binary max-heap implemented using an array. Which one of the following
array represents a binary max-heap? (GATE CS 2009)
(A) 25,12,16,13,10,8,14 (B) 25,12,16,13,10,8,14
(C) 25,14,16,13,10,8,12 (D) 25,14,12,13,10,8,16
Ans:- Option (C) 25,14,16,13,10,8,12
Explanation:- A tree is max-heap if data at every node in the tree is greater than or equal
to it’s children’ s data. In array representation of heap tree, a node at index i has its left
child at index 2i + 1 and right child at index 2i + 2.
Department of Information Technology, GCoE, Amravati Winter 2022