heap sort algorithm program using C language

-

 #include <stdio.h>


// Function to print tree structure from array

void printTree(int a[], int n) {

    for (int i = 0; i < n; i++) {

        int left = 2 * i + 1;

        int right = 2 * i + 2;


        printf("\nParent: %d", a[i]);


        if (left < n)

            printf(" | Left: %d", a[left]);

        else

            printf(" | Left: NULL");


        if (right < n)

            printf(" | Right: %d", a[right]);

        else

            printf(" | Right: NULL");

    }

    printf("\n-------------------------\n");

}


// Function to heapify a subtree rooted at index i

void heapify(int a[], int n, int i) {

    int largest = i;          // Root index

    int left = 2 * i + 1;     // Left child

    int right = 2 * i + 2;    // Right child


    // If left child is larger than root

    if (left < n && a[left] > a[largest])

        largest = left;


    // If right child is larger than largest so far

    if (right < n && a[right] > a[largest])

        largest = right;


    // If largest is not root

    if (largest != i) {

        int temp = a[i];

        a[i] = a[largest];

        a[largest] = temp;


        // Recursively heapify the affected subtree

        heapify(a, n, largest);

    }

}


// Heap Sort function

void heapSort(int a[], int n) {

    // Build heap (rearrange array)

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

        heapify(a, n, i);


    printf("Max Heap built:\n");

    printTree(a, n);


    // One by one extract elements

    for (int i = n - 1; i > 0; i--) {

        // Swap root (max) with last element

        int temp = a[0];

        a[0] = a[i];

        a[i] = temp;


        printf("After moving max %d to end:\n", a[i]);

        printTree(a, i); // Print remaining heap


        // Heapify reduced heap

        heapify(a, i, 0);

    }

}


int main() {

    int a[] = {1, 12, 3, 4,10,15};

    int n = sizeof(a) / sizeof(a[0]);


    printf("Original array:\n");

 for (int i = 0; i < n; i++)

        printf("%d ", a[i]);

   

 printTree(a, n);


    heapSort(a, n);


    printf("Sorted array: ");

    for (int i = 0; i < n; i++)

        printf("%d ", a[i]);

    printf("\n");


    return 0;

}




Output:-

Original array:


Parent: 1 | Left: 12 | Right: 3

Parent: 12 | Left: 4 | Right: 10

Parent: 3 | Left: 15 | Right: NULL

Parent: 4 | Left: NULL | Right: NULL

Parent: 10 | Left: NULL | Right: NULL

Parent: 15 | Left: NULL | Right: NULL

-------------------------

Max Heap built:


Parent: 15 | Left: 12 | Right: 3

Parent: 12 | Left: 4 | Right: 10

Parent: 3 | Left: 1 | Right: NULL

Parent: 4 | Left: NULL | Right: NULL

Parent: 10 | Left: NULL | Right: NULL

Parent: 1 | Left: NULL | Right: NULL

-------------------------

After moving max 15 to end:


Parent: 1 | Left: 12 | Right: 3

Parent: 12 | Left: 4 | Right: 10

Parent: 3 | Left: NULL | Right: NULL

Parent: 4 | Left: NULL | Right: NULL

Parent: 10 | Left: NULL | Right: NULL

-------------------------

After moving max 12 to end:


Parent: 1 | Left: 10 | Right: 3

Parent: 10 | Left: 4 | Right: NULL

Parent: 3 | Left: NULL | Right: NULL

Parent: 4 | Left: NULL | Right: NULL

-------------------------

After moving max 10 to end:


Parent: 1 | Left: 4 | Right: 3

Parent: 4 | Left: NULL | Right: NULL

Parent: 3 | Left: NULL | Right: NULL

-------------------------

After moving max 4 to end:


Parent: 3 | Left: 1 | Right: NULL

Parent: 1 | Left: NULL | Right: NULL

-------------------------

After moving max 3 to end:


Parent: 1 | Left: NULL | Right: NULL

-------------------------

Sorted array: 1 3 4 10 12 15 



Comments

Post a Comment

Popular posts from this blog

B.tech 5th Sem Machin learning lab practical

-
 Program 1:   Implement and demonstrate the FIND-S algorithm for finding the most specific hypothesis   based on a  given set of training data samples. Read the training data from a .CSV file. import random import csv import pandas as pd att= [['Sunny','Rainy'],               ['Warm','Cold'],               ['Normal','High'],               ['Strong','Weak'],               ['Warm','Cool'],               ['Same','Change']] attribute=len(att) print("attribute length=",attribute) print("\n Most general hypothesis:['?','?','?','?,'?','?']") print("\n Most specific hypothesis:['0','0','0','0','0','0']") a=[] print("\n Given training data set") with open('C:\\Users\pc1\\Desktop\\machine\\ws.csv') as file:     reader=csv.reader(file)     for r in reader:       ...
Read more

DWDM 2024 question paper with solution

-
Image
  Question paper DWDM  2024.    https://www.abesit.in/wp-content/uploads/2024/11/KOE093-DATA-WAREHOUSING-DATA-MINING.pdf Solution DWDM 2024  Solution of DWDM paper 2024 SECTION A – Attempt all questions in brief (2 marks each) a. Define Data Warehousing. A data warehouse is a centralized repository that stores integrated data from multiple sources, enabling analysis, reporting, and decision-making. b. Discuss the Fact Constellation. Fact Constellation is a schema that contains multiple fact tables sharing dimension tables, also known as galaxy schema, suitable for complex databases. c. Explain Distributed DBMS implementation. A Distributed DBMS manages a database distributed across multiple locations, ensuring transparency, consistency, and coordination of data across sites. d. Define Warehousing Software. Warehousing software is a tool or application used to construct, manage, and access a data warehouse for efficient data integration, analysis, and reporting....
Read more

BCA 3rd year Web Technology(code 304) Web Site development using ASP.NET AND C#

-
Image
  Web Site development using ASP.NET AND C# UNIT – I Overview of ASP.NET framework, Understanding ASP.NET Controls, Applications, Web servers, installation of IIS. Web forms, web form controls -server controls, client controls, web forms & HTML, Adding controls to a web form ,Buttons, Text Box , Labels, Checkbox, Radio Buttons, List Box, etc. Running a web Application, creating a multiform web project. UNIT- II Form Validation: Client side validation, server Side validation, Validation Controls : Required Field Comparison Range. Calendar control, Ad rotator Control, Internet Explorer Control. State management- View state, Session state, Application state, UNIT- III Architecture of ADO.NET, Connected and Disconnected Database, Create Connection using ADO.NET Object Model, Connection Class, Command Class, DataAdapter Class, Dataset Class. Display data on data bound Controls and Data Grid. Database Accessing on web applications: Data Bind...
Read more