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 ...
Read more

Reading and Writing Text Files

Handling text files in Java involves performing operations like reading from, writing to, and appending to files. Here are some common techniques and examples for handling text files in Java: FileReader and BufferedReader are classes in Java used for reading text from files. Here’s a detailed explanation of each: FileReader FileReader is a class in Java that is used to read character files. It is a convenient class for reading text files using the default character encoding of the operating system. Key Points: Purpose : To read text files. Inheritance : It extends InputStreamReader , which in turn extends Reader . Encoding : Uses the default character encoding of the operating system unless specified otherwise. Basic Usage : Suitable for simple file reading tasks. Example: create a text file "example.txt" using any text editor and then run this program.In this example, FileReader reads the file character by character. import java.io.FileReader; import java.io.IOException; ...
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....
Read more