forked from krimanisha/Hacktoberfest21
-
Notifications
You must be signed in to change notification settings - Fork 0
/
HeapSort.java
81 lines (72 loc) · 2.24 KB
/
HeapSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package Sorting;
/*
Heap sort processes the elements by creating the min heap or max heap using
the elements of the given array. Min heap or max heap represents the ordering
of the array in which root element represents the minimum or maximum element
of the array. At each step, the root element of the heap gets deleted & stored
into the sorted array and the heap will again be heapified.
The heap sort basically recursively performs two main operations.
* Build a heap H, using the elements of ARR.
* Repeatedly delete the root element of the heap formed in phase 1.
*/
public class HeapSort {
public void heapSort(int arr[])
{
int temp;
//build the heap
for (int i = arr.length / 2 - 1; i >= 0; i--)
{
heapify(arr, arr.length, i);
}
//extract elements from the heap
for (int i = arr.length - 1; i > 0; i--)
{
//move current root to end (since it is the largest)
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//recall heapify to rebuild heap for the remaining elements
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i)
{
int MAX = i; // Initialize largest as root
int left = 2 * i + 1; //index of the left child of ith node = 2*i + 1
int right = 2 * i + 2; //index of the right child of ith node = 2*i + 2
int temp;
//check if the left child of the root is larger than the root
if (left < n && arr[left] > arr[MAX])
{
MAX = left;
}
//check if the right child of the root is larger than the root
if (right < n && arr[right] > arr[MAX])
{
MAX = right;
}
//repeat the procedure for finding the largest element in the heap
if (MAX != i)
{
temp = arr[i];
arr[i] = arr[MAX];
arr[MAX] = temp;
heapify(arr, n, MAX);
}
}
//display the array
void display(int arr[])
{
for (int i=0; i<arr.length; ++i)
{
System.out.print(arr[i]+" ");
}
}
public static void main(String args[])
{
int arr[] = { 12, 33, 52, 1, 12, 9 , 3, 10, 15 };
HeapSort sort = new HeapSort();
sort.heapSort(arr);
sort.display(arr);
}
}