Scribd
Upload
12 views

Data sturcture and algorithm week 9

Uploaded by

hm896980
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views

Data sturcture and algorithm week 9

Uploaded by

hm896980
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

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

You might also like