Scribd Logo
Upload

Welcome to Scribd!

  • 63 views

    DSA Assignment 3

    Uploaded by

    FATIMA NASIR AWAN
    This document is a student assignment submission for a data structures and algorithms class. It contains code for implementing max and min heap data structures. The code includes functions for heapifying a tree, inserting and deleting nodes, and extracting the max/min values. The main function tests the max and min heap implementations on a sample array and outputs the results.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    DSA Assignment 3

    Uploaded by

    FATIMA NASIR AWAN
    63 views5 pages
    This document is a student assignment submission for a data structures and algorithms class. It contains code for implementing max and min heap data structures. The code includes functions for heapifying a tree, inserting and deleting nodes, and extracting the max/min values. The main function tests the max and min heap implementations on a sample array and outputs the results.

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document is a student assignment submission for a data structures and algorithms class. It contains code for implementing max and min heap data structures. The code includes functions for heapifying a tree, inserting and deleting nodes, and extracting the max/min values. The main function tests the max and min heap implementations on a sample array and outputs the results.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    63 views5 pages

    DSA Assignment 3

    Uploaded by

    FATIMA NASIR AWAN
    This document is a student assignment submission for a data structures and algorithms class. It contains code for implementing max and min heap data structures. The code includes functions for heapifying a tree, inserting and deleting nodes, and extracting the max/min values. The main function tests the max and min heap implementations on a sample array and outputs the results.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    Department of Creative Technologies

    Subject
    Data Structures & Algorithms

    Instructor:
    Adnan Aslam

    Name: Fatima Nasir Awan


    Reg ID: 212015
    Section: BSSE-III-A
    Assignment No: 03
    Date of Submission: 13th Oct 2022
    Max & Min Heap Code:

    INPUT:
    #include<iostream>
    using namespace std;

    void swap(int *a, int *b)


    {
    int temp = *a;
    *a = *b;
    *b = temp;
    }

    void heapify(int arr[], int &N, int i)


    {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < N && arr[l] > arr[largest])


    largest = l;

    if (r < N && arr[r] > arr[largest])


    largest = r;

    if (largest != i) {
    swap(arr[i], arr[largest]);
    heapify(arr, N, largest);
    }
    }

    void MinHeapify(int arr[], int &N, int i)


    {
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < N && arr[l] < arr[smallest])


    smallest = l;

    if (r < N && arr[r] < arr[smallest])


    smallest = r;

    if (smallest != i) {
    swap(arr[i], arr[smallest]);
    MinHeapify(arr, N, smallest);
    }
    }

    void MaxHeap(int arr[], int &N)


    {

    int startIdx = (N / 2) - 1;

    for (int i = startIdx; i >= 0; i--) {


    heapify(arr, N, i);
    }
    }
    void MinHeap(int arr[], int &N)
    {

    int startIdx = (N / 2) - 1;

    for (int i = startIdx; i >= 0; i--) {


    MinHeapify(arr, N, i);
    }
    }
    //
    void deleteNode(int arr[], int& N)
    {
    int lastElement = arr[N - 1];

    arr[0] = lastElement;

    N=N-1;

    heapify(arr, N, 0);
    }

    void printHeap(int arr[], int &N)


    {
    for (int i = 0; i < N; ++i)
    cout << arr[i] << " ";
    cout << "\n";
    }
    void insertNode(int arr[], int key, int &N)
    {
    N = N+1;
    arr[N-1] = key;
    heapify(arr,N,N-1);
    }
    //ExtractMax from Max Heap
    int peekMax(int arr[])
    {
    return arr[0];
    }
    //ExtractMax from Min Heap
    int peekMin(int arr[], int &N)
    {
    return arr[N-1];
    }

    int main()
    {
    int arr[] = {3,9,2,1,4,5};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"MinHeap: \n";
    MinHeap(arr, N);
    printHeap(arr,N);
    cout<<"ExtractMax: "<<peekMin(arr,N)<<endl;
    cout<<"Removing highest priority element from Heap: \n";
    deleteNode(arr,N);
    printHeap(arr,N);
    cout<<"MaxHeap: \n";
    // insertNode(arr,7,N);
    MaxHeap(arr,N);
    printHeap(arr, N);
    cout<<"Removing highest priority element from Heap: \n";
    deleteNode(arr, N);
    printHeap(arr,N);
    cout<<"ExtractMax: "<<peekMax(arr);

    OUTPUT:
    THANKYOU.

    You might also like