-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeaps.java
More file actions
66 lines (60 loc) · 1.75 KB
/
Heaps.java
File metadata and controls
66 lines (60 loc) · 1.75 KB
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
import java.util.Arrays;
import java.util.Scanner;
public class Heaps {
public static int parent(int i) { return i/2; }
public static int left(int i) { return i*2+1;}
public static int right(int i) { return i*2 + 2;}
public static int extractMinMax(int a[], int n) {
int t = a[0];
a[0] = a[n-1];
a[n-1] = t;
n--;
heapifyMin(a, 0, n);
return t;
}
public static void heapifyMin(int a[], int i, int n){
int mI = i;
if(left(i)<n && a[left(i)] < a[mI]) mI = left(i);
if(right(i) < n && a[right(i)] < a[mI]) mI = right(i);
if(mI != i) {
int t = a[i];
a[i] = a[mI];
a[mI] = t;
heapifyMin(a, mI, n);
}
}
public static void heapifyMax(int a[], int i, int n){
int mI = i;
if(left(i)<n && a[left(i)] > a[mI]) mI = left(i);
else if(right(i) < n && a[right(i)] > a[mI]) mI = right(i);
if(mI != i) {
int t = a[i];
a[i] = a[mI];
a[mI] = t;
heapifyMax(a, mI, n);
}
}
public static void buildHeap(int a[], int n) {
for(int i= n/2-1;i>=0;i--) {
heapifyMin(a,i,n);
}
}
public static void insert(int a[], int val, int n) {
n = n+1;
a[n] = val;
heapifyMin(a, parent(n), n);
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int k = 4;
int a[] = {7, 10, 4, 20, 15};
int n = a.length;
buildHeap(a, n);
for(int i=0;i<k-1;i++) {
extractMinMax(a,n);
n = n-1;
}
System.out.println(extractMinMax(a,n));
//System.out.println(Arrays.toString(a));
}
}