DAA

1. Explain the run time complexity of heap sort.

ANS- Heap sort has a time complexity of O(n log n) in all cases, including best-case,
average-case, and worst-case scenarios.

Here's a breakdown of why:

• Heapify: The heap sort algorithm relies on a heap data structure. Building the
initial heap from the input array involves a process called heapify, which takes
O(n) time in the worst case.
• Extracting Maximum: Extracting the largest element (in the case of sorting in
ascending order) and placing it in its final position is done repeatedly. This
operation takes O(log n) time because it involves rearranging elements within the
heap to maintain the heap property.
• Repetition: This process of extracting the maximum and fixing the heap is
repeated n times (once for each element to be placed in its final sorted position).

Since the dominant factor is the repeated extraction and heapify operations (n * O(log
n)), the overall time complexity of heap sort becomes O(n log n).

[Remembering:5]
2. Sort the following numbers in ascending order by using heapsort technique? [Understanding:5]
5,9,2,7,1,8,3,4
ANS- Sorted array is:
[1, 2, 3, 4, 5, 7, 8, 9]
3. What is a heap? What is a binary heap, and how do you implement it?

ANS- A heap is a tree-based data structure that efficiently implements a priority queue. It
follows a specific order property:

• Max Heap: In a max heap, the value of a parent node is always greater than or equal to
the values of its children. The largest element (with the highest priority) resides at the
root.
• Min Heap: In a min heap, the value of a parent node is always less than or equal to the
values of its children. The smallest element (with the highest priority) resides at the root.

Both types are useful for prioritizing elements based on their values. Common
operations on heaps include:

• Insert: Add a new element to the heap while maintaining the heap property.
• Extract Max/Min: Remove and return the element with the highest (max heap) or lowest
(min heap) priority from the root.
• Decrease/Increase Key: Modify the value of an existing element while upholding the
heap property.

Page 1
 DAA
Binary Heap: A Specific Type of Heap

A binary heap is a particular implementation of a heap where each node has at most
two child nodes.

Here's a C implementation of a binary heap:

C
#include <stdio.h>
#include <limits.h>

#define MAX_SIZE 100 // Adjust this value based on your needs

// Function prototypes
void swap(int *a, int *b);
void heapify(int arr[], int n, int i);
void insert(int arr[], int *size, int value);
void deleteRoot(int arr[], int *size);
void printHeap(int arr[], int size);

int main() {
int arr[MAX_SIZE];
int size = 0;

insert(arr, &size, 5);

insert(arr, &size, 9);
insert(arr, &size, 2);
insert(arr, &size, 7);
insert(arr, &size, 1);

printf("Heap elements after insertion: \n");

printHeap(arr, size);

deleteRoot(arr, &size);

printf("Heap elements after deletion: \n");

printHeap(arr, size);

return 0;
}

// Swap two integers

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Heapify function to maintain heap property after insertion or deletion

void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2

// If left child is larger than

Pageroot
2
 DAA
if (left < n && arr[left] > arr[largest])
largest = left;

// If right child is larger than largest so far

if (right < n && arr[right] > arr[largest])
largest = right;

// If largest is not root

if (largest != i) {
swap(&arr[i], &arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

// Insert a new element into the heap

void insert(int arr[], int *size, int value) {
if (*size == MAX_SIZE) {
printf("Heap overflow\n");
return;
}

arr[*size] = value; // Insert at the end

(*size)++;

int i = *size - 1;
// Heapify bottom-up to maintain max-heap property
while (i > 0 && arr[parent(i)] < arr[i]) {
swap(&arr[i], &arr[parent(i)]);
i = parent(i);
}
}

// Get parent index

int parent(int i) {
return (i - 1) / 2;
}

// Remove and return the element with the highest priority (root)
void deleteRoot(int arr[], int *size) {
if (*size == 0) {
printf("Heap underflow\n");
return;
}

// Move the last element to the root

arr[0] = arr[*size - 1];
(*size)--;

// Heapify top-down to maintain max-heap property

heapify(arr, *size, 0);
}

// Print the heap elements

void printHeap(int arr[], int size) {
for (int i = 0; i < size; ++i)
printf("%d ", arr[i]); Page 3
 DAA
printf("\n");
}
Use code with caution.
content_copy

This code defines the following functions:

• swap: Swaps two integers.

• heapify: Maintains the max-heap property by comparing a node with its children
and swapping if necessary.
• insert: Inserts a new element into the heap and calls heapify to maintain the
heap property.
• deleteRoot: Removes and returns the root element (highest priority) and calls
heapify to maintain the heap property.
• printHeap: Prints the elements of the heap.

The main function demonstrates how to use these functions to create a heap, insert
elements, delete the root, and print the heap contents.

[Analysing:5]
4. What are some ways to implement priority queue?

ANS- Priority queues can be implemented using various data structures, each with its
own advantages and trade-offs. Here are some common approaches:

1. Heaps: This is the most efficient and widely used method for implementing a
priority queue. Heaps are tree-based data structures that maintain a specific
order property. In a max-heap, the element with the highest priority resides at the
root, and its children have progressively lower priorities. Conversely, in a min-
heap, the lowest priority element sits at the root.
o Advantages: Heaps offer efficient insertion (O(log n)) and removal of the
highest/lowest priority element (O(log n)) due to their well-defined
structure.
o Disadvantages: Heaps can be less efficient for some operations like
finding an arbitrary element or deleting a specific element within the queue
(O(n) in the worst case).
2. Binary Search Trees (BSTs): BSTs are ordered trees where each node's value
is greater than all elements in its left subtree and less than all elements in its right
subtree. Priority can be associated with the element's value, with higher values
having higher priority.
o Advantages: BSTs allow for efficient searching (O(log n) on average) and
potentially faster deletion of specific elements compared to heaps (O(log
n) on average).

Page 4
 DAA
o Disadvantages: Insertion and deletion can become O(n) in the worst case
for unbalanced trees. Additionally, extracting the highest/lowest priority
element might require traversing the entire tree.
3. Ordered Arrays: A simple approach is to maintain an array where elements are
inserted in descending (max-heap) or ascending (min-heap) order based on their
priority.
o Advantages: This method is easy to understand and implement, and
accessing the highest/lowest priority element is very fast (O(1)).
o Disadvantages: Insertion requires shifting elements to maintain order,
leading to O(n) complexity in the worst case. Deleting an element also
involves shifting, resulting in potentially slow performance (O(n)).
4. Fibonacci Heaps: This is a specialized type of heap that offers amortized
constant time (O(1)) for most operations like insertion, deletion, and finding the
minimum element. However, their implementation is more complex compared to
simpler heaps.

[Applying:5]
5. Explain how Heap Sort works.

ANS- Heap sort is a comparison-based sorting algorithm that leverages the efficient
properties of heaps to sort an array in ascending order (or descending order if desired).
Here's a breakdown of how it works:

1. Building the Heap:

• The algorithm starts by treating the input array itself as a collection of unsorted
elements.
• It then rearranges the elements in the array to form a max-heap. In a max-heap,
the parent node has a value greater than or equal to both its child nodes. This
process ensures that the largest element in the array ends up at the root of the
heap.

2. Extracting Maximum and Sorting:

• Once the heap is built, the largest element (at the root) is extracted from the heap
and placed at the end of the original array. This effectively puts the largest
element in its final sorted position.
• To maintain the heap property, the remaining elements in the heap are
"heapified" again. Heapify refers to a process that adjusts the heap structure to
ensure the largest element remains at the root.

3. Repetition:

• Steps 2 (extract max and heapify) are repeated n-1 times (where n is the number
of elements in the array). With each iteration, the largest remaining element is
extracted, placed at its final sorted position, and the heap is adjusted accordingly.
Page 5
 DAA
4. Result:

• After n-1 extractions and heapifications, all elements will be placed in their correct
sorted positions within the original array, with the smallest element at the
beginning and the largest at the end (ascending order).

Time Complexity:

• Heap sort has a time complexity of O(n log n) in all cases, including best-case,
average-case, and worst-case scenarios. This is because building the initial heap
and subsequent heapify operations involve logarithmic time (O(log n)) for each
element.

Advantages:

• Heap sort is efficient for both random and partially sorted data.
• It has a relatively simple implementation compared to some other sorting
algorithms.
• It sorts data in-place, meaning it modifies the original array without requiring
significant additional memory allocation.

Disadvantages:

• Heap sort might not be the most efficient choice for very small data sets, as there
are faster algorithms for such cases.

Example:

Consider an array [5, 9, 2, 7, 1, 8, 3, 4]. Here's a simplified visualization of how

heap sort would work:

1. Build a max-heap from the array: [9, 8, 7, 5, 1, 2, 3, 4]

2. Extract the maximum (9) and place it at the end of the array: [5, 8, 7, 2, 1, 3,
4, 9] (heapify the remaining elements)
3. Extract the maximum (8) and place it at the second-last position: [5, 7, 3, 2,
1, 4, 8, 9] (heapify)
4. Repeat steps 2 and 3 until all elements are sorted, resulting in the final sorted
array: [1, 2, 3, 4, 5, 7, 8, 9]

Page 6