Heap Sort - Java

import java.util.*;

class Sort 
{
    
    int a[],n,ne;
    Scanner s=new Scanner(System.in);
    void read()
    {

     System.out.println("Enter number of elements...");
     n=s.nextInt();
     ne=n;
     a=new int[n];
     System.out.println("Enter the elements..");
     for(int i=0;i<n;i++)
     a[i]=s.nextInt();
    }
     
    void display()
    {

    System.out.println("Sorted List..");
     for(int i=0;i<n;i++)
     System.out.println(a[i]);
    }


    void heapsort() 
    {
        //build heap structure
        buildheap();
        //extract maxima
        extractmax();
    }

    void buildheap() 
    {
        //let heap grow from half size to entire size
        for(int i=n/2-1; i>=0; i--) 
        {
            heapify(i,n);
        }
    }

     void extractmax() 
     {
         //n is separator between heap and sorted part
        while (ne>1) 
            {
            ne--;
            //put maximum at the end of heap
            swap(0,ne);
            //restore heap
            heapify(0,ne);
            }
      }

    //restore heap invariant
     void heapify(int i, int n) 
     {
        int k=2*i+1; //first child of i
        while (k<n) 
        {
            //if another child exists and that child is the maximum
            if (k+1<n && a[k+1]>a[k]) k++;

            if (a[i]>=a[k]) 
            {
                return; //heap invariant restored
            } else 
            {
                //swap element with its child
                swap(i, k);

                //continue with next iteration
                i=k;
                k=2*i+1;
            }
        }
    }

     void swap (int i, int j) 
     {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
     }
}

class Main
 {
public static void main(String args[])
 {

  Sort s=new Sort();
  s.read();
  s.heapsort();
  s.display();  

  }
}

Comments

Post a Comment

Popular posts from this blog

KTU OOP LAB JAVA CSL 203 BTech CS S3 - Dr Binu V P

About Me Scheme and Evaluation Syllabus and Practice Questions ******************************** How to do Java Programs in  Debian PART A Basic Java Programs Using Control  Statements 1.String Problems 2.Numerical Problems 3.Arrays 4.Matrix Lab Exercise Java-1 PART B  Object Oriented Programming 1.Creating classes and objects. constructor for initializing object 2.Method overloading in Java 3.Single Inheritance 4.Multilevel Inheritance 5.Method overriding in Java 6. Hierarchical Inheritance 7.Interface in Java 8.Abstract classes in java  PART C Exception and File Handling 1.Exception Handling in Java 2.Reading and Writing Text Files 3.Buffered Reader and String Tokenizer PART D Multi-Threading  Creating Threads in Java Thread Synchronization in Java Thread Priorities in Java Programs using Multi-Threading PART E Graphics and Database Programming Introduction to Java Swing Drawing Shapes Drawing  a Sine Wave Handling Mouse Events Handling Keyboard Events Drawing Shapes with Mouse Events
Read more

Syllabus and Practice Questions KTU OOPS Lab Java CSL 203

SYLLABUS The syllabus contains six sessions (A, B, C, D, E, F). Each session consists of three concrete Java exercises, out of which at least two questions are mandatory. (A) Basic programs using datatypes, operators, and control statements in Java. 1) Write a Java program that checks whether a given string is a palindrome or not. Ex: MALAYALAM is palindrome. 2) Write a Java Program to find the frequency of a given character in a string. ** 3) Write a Java program to multiply two given matrices. ** (B) Object Oriented Programming Concepts: Problem on the use of constructors, inheritance,  method overloading & overriding, polymorphism and garbage collection: 4) Write a Java program which creates a class named 'Employee' having the following  members: Name, Age, Phone number, Address, Salary. It also has a method named 'print-Salary( )' which prints the salary of the Employee. Two classes 'Officer' and 'Manager' inherits the 'Employee' class. T
Read more

String Problems

Reverse a String import java.util.Scanner; public class ReverseString { public static void main(String[] args) {      Scanner scanner = new Scanner(System.in);      System.out.print("Enter a string to reverse: ");      String input = scanner.nextLine();      String reversed = new StringBuilder(input).reverse().toString();      System.out.println("Reversed string: " + reversed);      scanner.close(); } } without using StringBuilder import java.util.Scanner; public class ReverseString {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         System.out.print("Enter a string to reverse: ");         String input = scanner.nextLine();         // Manually reverse the string         String reversed = "";         for (int i = input.length() - 1; i >= 0; i--) {             reversed += input.charAt(i);         }         System.out.println("Reversed string: " + reversed);                  scanner.c
Read more