ASSIGNMENT WEEK – 9
Name – HIMANSHU RAJ
Register No. - EA2331201010152
Program - B.C.A.-Data Science
Subject – Data Structure & Algorithm (DSA)
Semester – II Semester
EA2331201010152
1. State & explain the algorithm to perform Heap sort. Also analyze the time
complexity of the algorithm.
Ans. Heap Sort Algorithm
Heap sort is a comparison-based sorting algorithm that utilizes a heap data structure to
efficiently order elements. Here's the algorithm breakdown:
Steps:
1. Build a Max-Heap:
o Arrange the input data in a max-heap structure. In a max-heap, the parent node
is always greater than or equal to its children.
o You can use various methods to create a heap, including bottom-up heap
construction or using heapify operations.
2. Extract Maximum Repeatedly:
o Repeatedly perform the following:
▪ Swap the root element (largest in a max-heap) with the last element of the
heap.
▪ Reduce the heap size by 1 (exclude the last element).
▪ Heapify the remaining elements to maintain the max-heap property.
3. Result:
o After all extractions, the elements in the reduced heap will be in descending
order (largest at the beginning). Reversing this order provides the sorted data in
ascending order.
Time Complexity:
• Best Case: O(n log n) - This occurs when the input data is already sorted in
descending order (already a max-heap). The heapify operations for extraction take
logarithmic time (log n) and are repeated n times.
• Average Case: O(n log n) - For most random inputs, the average time complexity
remains the same as the best case. Building the heap and the extraction process with
heapify take n log n time on average.
• Worst Case: O(n log n) - This happens when the input data is sorted in ascending
order (opposite of a max-heap). Reversing the sorted elements after extraction takes
additional linear time (n), but the dominant factor is still the heap operations (n log n).
2. Construct Minheap structure for the initial key set 42, 23, 74,11,
65,58,94,36,99,87.
Ans. Constructing Min-Heap for [42, 23, 74, 11, 65, 58, 94, 36, 99, 87]
For demonstration purposes, we'll build a min-heap instead of a max-heap as the
core concept remains the same. In a min-heap, the parent node is always less than or
equal to its children. Here's how we can construct the min-heap:
EA2331201010152
Steps:
1. Start with an empty heap.
2. Insert the first element (42) into the heap. The heap now has just one element,
which is the root by default.
3. Insert the next element (23). Compare it with the root (42). Since 23 is less,
swap it with the root and then heapify (reorganize) to maintain the min-heap
property (swapping parent and child if the child is smaller). The heap becomes:
{23, 42}.
4. Repeat for remaining elements:
o Insert 74: {23, 42, 74} (no swap needed, 74 goes to the right of 42).
o Insert 11: {11, 23, 74, 42} (swap 23 and 11).
o Insert 65: {11, 23, 74, 42, 65} (heapify from the bottom, might involve
swapping 65 with 42).
o Insert 58: {11, 23, 58, 42, 65, 74} (similar to 65, might involve swaps).
o Insert 94: {11, 23, 58, 42, 65, 74, 94} (similar to 65 and 58).
o Insert 36: {11, 23, 36, 42, 65, 74, 94, 58} (similar to previous insertions).
o Insert 99: {11, 23, 36, 42, 65, 74, 94, 58, 99} (similar to previous
insertions).
o Insert 87: {11, 23, 36, 42, 65, 74, 94, 58, 99, 87} (similar to previous
insertions).
Resulting Min-Heap:
11
/
EA2331201010152
