Assignment: Heaps | DSA in C++ - Software Development PDF Download

Instructions

• This assignment is designed to test your understanding of Heaps and Priority Queues in C++.
• Read each question carefully and select the most appropriate answer or fill in the blank as required.
• Some questions may require coding or hands-on implementation.
• Attempt all the questions.
• Detailed answers to all the questions are provided at the end of the worksheet.

MCQs (Multiple Choice Questions)

Q.1. Which data structure is commonly used to implement priority queues?
(a) Arrays
(b) Stacks
(c) Queues
(d) Heaps

Ans. (d)

Q.2. What is the time complexity of inserting an element into a heap of size N?
(a) O(log N)
(b) O(N)
(c) O(N log N)
(d) O(1)

Ans. (a)

Q.3. In a max-heap, the maximum element is always present at which position?

(a) Root node
(b) Left child of the root
(c) Right child of the root
(d) Any leaf node

Ans. (a)

Q.4. Which operation is used to remove the maximum element from a max-heap?
(a) Extract-Min
(b) Extract-Max
(c) Delete-Min
(d) Delete-Max

Ans. (b)

Q.5. Which of the following is NOT a valid way to create a min-heap in C++?

(a) Using a priority_queue container
(b) Using the make_heap() function
(c) Using the push_heap() function
(d) Using the sort_heap() function

Ans. (d)

HOTS (Higher Order Thinking Questions)

Q.1. Explain the concept of a binary heap and its types.

A binary heap is a complete binary tree that satisfies the heap property. In a binary heap, the value of each node is greater than or equal to the values of its children in a max-heap (max-heap property), and the value of each node is less than or equal to the values of its children in a min-heap (min-heap property). There are two types of binary heaps: max-heap and min-heap.

Q.2. How does a heap differ from a regular binary tree?

Unlike a regular binary tree, a heap must satisfy the heap property. In a max-heap, the value of each node is greater than or equal to the values of its children, whereas in a min-heap, the value of each node is less than or equal to the values of its children. Additionally, a heap is a complete binary tree, meaning all levels except the last are fully filled, and the last level is filled from left to right.

Q.3. Describe the process of deleting an element from a heap.

Deleting an element from a heap involves replacing the element to be deleted with the last element in the heap, removing the last element, and then performing a heapify operation to restore the heap property. In a max-heap, the replaced element is moved down the heap by swapping it with its larger child until it satisfies the heap property.

Q.4. Discuss the advantages and use cases of priority queues in real-world applications.

Priority queues have several advantages and real-world applications. They allow efficient retrieval of the element with the highest (or lowest) priority, making them suitable for scheduling, task management, and event handling systems. Priority queues are used in algorithms like Dijkstra's algorithm, Prim's algorithm, and Huffman coding. They can be implemented using heaps, which provide efficient operations like insertion, deletion, and retrieval of the highest (or lowest) priority element.

Q.5. Can a heap be empty? Explain your answer.

No, a heap can never be empty. At the very least, a heap must have a root node. However, a heap can contain only one element, making it the minimum and maximum value in the heap simultaneously.

Fill in the Blanks

1. In a binary heap, the value of each node is __________ than or equal to the values of its children in a max-heap.

greater

2. The __________ operation in a priority queue retrieves and removes the element with the highest priority.

pop or dequeue

3. The process of rearranging elements in a heap to maintain the heap property is called __________.

heapify or sift

4. The time complexity of building a heap from an array of size N is __________.

O(N)

5. The __________ function is used to insert an element into a heap.

push or enqueue

True or False

1. A heap is a complete binary tree. (True/False)

True

2. Heapsort is an efficient sorting algorithm based on the heap data structure. (True/False)

True

3. A binary heap can be represented using an array. (True/False)

True

4. A min-heap is the same as a max-heap with the order of elements reversed. (True/False)

False

5. The top() function in C++ priority_queue returns the minimum element in a min-heap. (True/False)

False

Hands-On Questions

Q.1. Implement a max-heap in C++ using an array and provide the code.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void maxHeapify(vector<int>& heap, int i, int size) {

    int largest = i;

    int left = 2 * i + 1;

    int right = 2 * i + 2;

    if (left < size && heap[left] > heap[largest])

        largest = left;

    if (right < size && heap[right] > heap[largest])

        largest = right;

    if (largest != i) {

        swap(heap[i], heap[largest]);

        maxHeapify(heap, largest, size);

    }

}

void buildMaxHeap(vector<int>& heap) {

    int size = heap.size();

    for (int i = (size / 2) - 1; i >= 0; --i)

        maxHeapify(heap, i, size);

}

int main() {

    vector<int> heap = {10, 20, 15, 30, 40};

    buildMaxHeap(heap);

    cout << "Max-Heap: ";

    for (int num : heap)

        cout << num << " ";

    return 0;

}

Q.2. Given an array of integers, write a C++ function to build a min-heap from the array.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void minHeapify(vector<int>& heap, int i, int size) {

    int smallest = i;

    int left = 2 * i + 1;

    int right = 2 * i + 2;

    if (left < size && heap[left] < heap[smallest])

        smallest = left;

    if (right < size && heap[right] < heap[smallest])

        smallest = right;

    if (smallest != i) {

        swap(heap[i], heap[smallest]);

        minHeapify(heap, smallest, size);

    }

}

void buildMinHeap(vector<int>& heap) {

    int size = heap.size();

    for (int i = (size / 2) - 1; i >= 0; --i)

        minHeapify(heap, i, size);

}

int main() {

    vector<int> heap = {30, 20, 10, 15, 40};

    buildMinHeap(heap);

    cout << "Min-Heap: ";

    for (int num : heap)

        cout << num << " ";

    return 0;

}

Q.3. Write a C++ function to delete the minimum element from a min-heap and provide the code.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void minHeapify(vector<int>& heap, int i, int size) {

    int smallest = i;

    int left = 2 * i + 1;

    int right = 2 * i + 2;

    if (left < size && heap[left] < heap[smallest])

        smallest = left;

    if (right < size && heap[right] < heap[smallest])

        smallest = right;

    if (smallest != i) {

        swap(heap[i], heap[smallest]);

        minHeapify(heap, smallest, size);

    }

}

int deleteMin(vector<int>& heap) {

    if (heap.empty())

        return -1;  // Heap is empty

    int minValue = heap[0];

    int lastValue = heap.back();

    heap[0] = lastValue;

    heap.pop_back();

    minHeapify(heap, 0, heap.size());

    return minValue;

}

int main() {

    vector<int> heap = {10, 20, 15, 30, 40};

    int minValue = deleteMin(heap);

    cout << "Min Value: " << minValue << endl;

    cout << "Heap: ";

    for (int num : heap)

        cout << num << " ";

    return 0;

}

Q.4. Implement a priority queue in C++ using a min-heap and provide the code.

#include <iostream>

#include <queue>

using namespace std;

int main() {

    priority_queue<int, vector<int>, greater<int>> pq;

    pq.push(5);

    pq.push(10);

    pq.push(3);

    pq.push(8);

    cout << "Priority Queue: ";

    while (!pq.empty()) {

        cout << pq.top() << " ";

        pq.pop();

    }

    return 0;

}

Q.5. Given a max-heap represented as an array, write a C++ function to extract the maximum element and provide the code.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int extractMax(vector<int>& heap) {

    if (heap.empty())

        return -1;  // Heap is empty

    int maxValue = heap[0];

    int lastValue = heap.back();

    heap[0] = lastValue;

    heap.pop_back();

    int size = heap.size();

    int i = 0;

    while (true) {

        int largest = i;

        int left = 2 * i + 1;

        int right = 2 * i + 2;

        if (left < size && heap[left] > heap[largest])

            largest = left;

        if (right < size && heap[right] > heap[largest])

            largest = right;

        if (largest != i) {

            swap(heap[i], heap[largest]);

            i = largest;

        } else {

            break;

        }

    }

    return maxValue;

}

int main() {

    vector<int> heap = {50, 30, 40, 20, 10};

    int maxValue = extractMax(heap);

    cout << "Max Value: " << maxValue << endl;

    cout << "Heap: ";

    for (int num : heap)

        cout << num << " ";

    return 0;

}