Heap sorting

Aim: - Implementation of Heap sort algorithm using Linked list as a data structure

The heap data structure is a special type of binary tree. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. The heap data structure can also be used for an efficient implementation of a priority queue. There are two types of heap

1.      Max-heap: All nodes of heap satisfy the relation that the key value at each node is at least as large as the value at its children

2.      Min-heap: All nodes of heap satisfy the relation that the key value at each node is at least as small as the value at its children

Heap sorting algorithm first organizes the data to be sorted into a heap. It does this with the following steps for sorting with max-heap

1.  Remove the topmost item (the largest) and replace it with the rightmost leaf

2.  Re-establish the heap

3.  Repeat steps 1 and 2 until there are no more items left in the heap 

     The following example shows the steps after heap as been constructed how sorting will work and how it adjust the heap.

Summary:- The complexity of the heap sort is O(nlog(n)). Heap sort is better option for large data sets. Unlike mergesort, heapsort requires no extra space. On the other hand, heapsort is not stable. A sorting algorithm is stable, if it leaves the order of equal elements unchanged.

Java Program to implement Heap sort algorithm using Linked list as a data structure

import java.util.*;

import java.io.*;

class Heap {

    LinkedList list= new LinkedList();

    int n;

    Heap(int x)  {

        n=x;

    }

    public void insert() throws IOException {

        DataInputStream in=new DataInputStream(System.in);

        int item;

        System.out.print("Enter any "+n+" integer elements");

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

        {

            item=Integer.parseInt(in.readLine());

            list.addLast(item);

        }

    }

    public void disp() throws IOException   {

            System.out.println(" "+list);

    }

    public void construct(int num) throws IOException   {

        int i,j,k,v;

        boolean heap;

        list.addFirst(0);

        for(i=num/2;i>0;i--)

        {

        k=i;

        v=Integer.valueOf(list.get(k).toString());

        heap =false;

        while(!heap && 2*k<=num) {

            j=2*k;

            if(j<num)

                if(Integer.valueOf(list.get(j).toString())<Integer.valueOf(list.get(j+1).toString()))

                    j++;

            if(v>=Integer.valueOf(list.get(j).toString()))

                    heap=true;

            else

           {

                list.set(k,list.get(j));     

                   k=j;

            }

        }

        list.set(k,v);

        }

        list.removeFirst();

    }

    public void sort() throws IOException {

      construct(n);

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

           Object temp=list.get(n-i);

           list.set(n-i, list.getFirst());

           list.set(0, temp);

           construct(n-i);

      }

   }

}

public class Sorting {

public static void main(String args[]) throws IOException {

    try{

        DataInputStream in=new DataInputStream(System.in);

        int count;

        System.out.println("Enter how many elements to be inserted");

        count=Integer.parseInt(in.readLine());

        Heap h1=new Heap(count);

        h1.insert();

        System.out.print(" Before sorting the list is ");

        h1.disp();

        h1.sort();

        System.out.print("\n After sorting the list is ");

        h1.disp();

       }

    catch(Exception e)   {

            System.out.println("Exception ="+e);

        }

    }

}

 

 

OUTPUT:

Enter how many elements to be inserted 8

Enter any 8 integer elements

8

7

6

5

4

4

3

2

 Before sorting the list is  [8, 7, 6, 5, 4, 4, 3, 2]

 After sorting the list is  [2, 3, 4, 4, 5, 6, 7, 8]