Lecture 327:- Deleting from Heap and Heap Sort

Deleting from a Heap: Deleting an element from a heap involves removing the root element (i.e., the maximum or minimum element, depending on whether it's a max heap or min heap) and rearranging the remaining elements to maintain the heap property. Here are the steps for deleting the root element from a max heap:

1. Replace the root (maximum) element with the last element in the heap.
2. Remove the last element from the heap (as it now contains the maximum element).
3. Heapify (bubble-down) the new root element to its correct position in the heap, ensuring that the heap property is maintained.

For a min heap, the process is similar, but instead of the maximum element, we remove the minimum element from the root.

Heap Sort: Heap sort is a comparison-based sorting algorithm that uses the concept of a heap to sort elements in ascending order (for max heap) or descending order (for min heap). The main steps of the heap sort algorithm are as follows:

1. Build a max heap (or min heap) from the input array.
2. Repeatedly extract the root element (maximum or minimum) from the heap, which is the largest (or smallest) element in the heap, and place it at the end of the array.
3. Reduce the size of the heap by one.
4. Heapify the remaining elements to maintain the heap property.
5. Repeat steps 2 to 4 until the entire array is sorted.

Here's a C++ program that demonstrates both deletion from a max heap and the heap sort algorithm:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to heapify (bubble-down) the element at a given index in a max heap void maxHeapify(vector<int>& heap, int index, int heapSize) {    int largest = index;    int leftChild = 2 * index + 1;    int rightChild = 2 * index + 2;    if (leftChild < heapSize && heap[leftChild] > heap[largest])        largest = leftChild;    if (rightChild < heapSize && heap[rightChild] > heap[largest])        largest = rightChild;    if (largest != index) {        swap(heap[index], heap[largest]);        maxHeapify(heap, largest, heapSize);    } } // Function to delete the root element (maximum) from a max heap void deleteMaxHeapRoot(vector<int>& heap) {    int n = heap.size();    if (n == 0) {        cout << "Heap is empty." << endl;        return;    }    // Replace root (maximum) with the last element    swap(heap[0], heap[n - 1]);    heap.pop_back(); // Remove the last element    // Heapify the new root to its correct position    maxHeapify(heap, 0, heap.size()); } // Function to perform Heap Sort on an input array void heapSort(vector<int>& arr) {    int n = arr.size();    // Build a max heap from the input array    for (int i = n / 2 - 1; i >= 0; i--)        maxHeapify(arr, i, n);    // Heap sort: repeatedly extract the root and place it at the end    for (int i = n - 1; i > 0; i--) {        swap(arr[0], arr[i]);        maxHeapify(arr, 0, i);    } } // Function to display the elements of the heap or array void display(const vector<int>& v) {    for (int val : v)        cout << val << " ";    cout << endl; } int main() {    vector<int> maxHeap = {30, 20, 15, 10, 5};    // Deleting the root element (maximum) from the max heap    cout << "Max Heap before deletion: ";    display(maxHeap);    deleteMaxHeapRoot(maxHeap);    cout << "Max Heap after deletion: ";    display(maxHeap);    // Using heap sort to sort an array in ascending order    vector<int> array = {10, 50, 30, 40, 20};    cout << "Original Array: ";    display(array);    heapSort(array);    cout << "Sorted Array (Ascending): ";    display(array);    return 0; }

In this program, the deleteMaxHeapRoot function deletes the root element from the max heap, and the heapSort function performs heap sort on an input array. The program demonstrates both the deletion from the max heap and the heap sort algorithm.