Heap
Sort
Heap
sort is works by finding the largest (or smallest) element of the list, placing
that at the end (or beginning) of the list, then continuing with the rest of
the list, to achieve the task only possible by using a data structure called a heap.
A heap is a special type of binary tree. After the data list has been arranged
into a heap, the root node (first node) is assured to be the largest (or
smallest) element. Then it is removed and placed at the end of the list, the
heap is reorganized, so the largest element keep moving to the root. The
process continues for the rest of the elements.
Graphical
Presentation of Heapify and Heap Sort
Complexity
Heap-Sort
takes O(log n) time, instead of O(n) for a linear searching as in simple
selection sort. This allows Heap sort to run in O(n log n) time.
·
Heap
sort is always O(n log n)
Quick sort is
usually O(n log n) but in the worst case slows to O(n2)
Quick sort is
generally faster, but Heap sort is better in time-critical applications
A loop of n
times (actually, n-1 times) used, because it keeps removing one of the n
nodes each time removing and replacing the root takes O(1) time
·
Therefore,
the total time is n times.
Since re-heap takes
place inside loop of n times, the total time for the loop is n*O(log n),
or O(n log n)
·
Where
heapifying takes O(n log n) time
The loop takes
O(n log n) time
Therefore,
total time is therefore O(n log n) + O(n log n)
This
is the same as O(n log n) time
Worst
case performance O(n log n)
Best
case performance Ω(n),O(n
log n)
Average
case performance O(n log n)
Algorithm
HeapSort(int
ar[], int n)
1. int i,j;
2. int lf, rt, mid, val, num;
3. val = (n-1)/2;
4. for j=val to 0 step -1
5. do
6. for i= val to 0 step -1
7. do
8. lf = (2*i)+1;
9. then
10. rt = (2*i)+2;
11. endif
12. if lf <= n and rt
<= n
13. then
14. if ar[rt] >=
ar[lf]
15.
then
16.
mid = rt;
17. else
18. mid = lf;
19. endif
20. else if(rt > n)
21. mid = lf;
22. else
23. mid = rt;
24. endif
25. if(ar[i] <
ar[mid])
26. then
27. num = ar[i];
28. ar[i] =
ar[mid];
29. ar[mid] =
num;
30. endif
31. endfor
32. num = ar[0];
33. ar[0] = ar[n];
34. ar[n] = num;
35. endfor
Pseudo
Code
HeapSort
BUILD_HEAP
heap-size
(A) ← length [A]
for
i ← length[A]/2 down to 1 do
Heapify (A, i)
HEAPSORT
BUILD_HEAP
(A)
for
i length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size
[A] ¬ heap-size [A] - 1
Heapify (A, 1)
Heapify
l ← left [i]
r ← right [i]
if
l ≤ heap-size [A] and A[l] > A[i]
then largest ← l
else largest ← i
if
r ≤ heap-size [A] and A[i] > A[largest]
then largest ← r
if
largest ← i
then exchange A[i] ↔ A[largest]
Heapify (A, largest)
Source
Code
import
java.io.*;
class Heap_Sort
{
void HeapSort(int ar[], int n)
{
int i,j;
int lf, rt, mid, val, num;
val = (n-1)/2;
for(j=val;j>=0;j--)
{
for(i=val;i>=0;i--)
{
lf =
(2*i)+1;
rt =
(2*i)+2;
if ((lf <=
n) && (rt <= n))
{
if(ar[rt] >=
ar[lf])
{
mid = rt;
}
else
{
mid = lf;
}
}
else
{
if(rt > n)
{
mid = lf;
}
else
{
mid = rt;
}
}
if (ar[i] <
ar[mid])
{
num
= ar[i];
ar[i] = ar[mid];
ar[mid] = num;
}
}
}
num = ar[0];
ar[0] = ar[n];
ar[n] = num;
}
void Input()throws IOException
{
BufferedReader Br=new
BufferedReader(new InputStreamReader(System.in));
int i;
System.out.print("\n\tEnter size of array : ");
int Size=Integer.parseInt(Br.readLine());
int Arr[]=new int[Size];
for(i=0;i<Size;i++)
{
System.out.print("\tEnter Element at Arr["+i+"] :
");
Arr[i]=Integer.parseInt(Br.readLine());
}
System.out.print("\n\tOriginal
: ");
Disp(Arr);
for(i=Size; i>1; i--)
{
HeapSort(Arr,i-1);
}
System.out.print("\n\tAfter Sort : ");
Disp(Arr);
}
void Disp(int Arr[])
{
for(int i=0 ;i<Arr.length;i++)
{
System.out.print(Arr[i]+"
");
}
}
//Main
Function
public static void main(String args[])throws IOException
{
Heap_Sort HS=new Heap_Sort();
HS.Input();
}
}
Output
Enter size of array : 5
Enter Element at Arr[0] : 5
Enter Element at Arr[1] : 1
Enter Element at Arr[2] : 2
Enter Element at Arr[3] : 9
Enter Element at Arr[4] : 6
Original :
5 1 2
9 6
After Sort : 1 2
5 6 9
No comments:
Post a Comment