forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgenericheap.java
More file actions
93 lines (74 loc) · 1.92 KB
/
Copy pathgenericheap.java
File metadata and controls
93 lines (74 loc) · 1.92 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.util.ArrayList;
import java.util.Comparator;
public class genericheap<T> { // create a generic heap class <T> , where T can be of any type.
private ArrayList<T> data = new ArrayList<>();
private Comparator<T> ctor;
public genericheap(Comparator<T> ctor) { // constructor to initialize the generic comparator
this.ctor=ctor;
}
public int size() { // returns the size of the arraylist data
return data.size();
}
public boolean isEmpty() { // checks whether the list is empty or not :: return true or false for the same
return data.isEmpty();
}
public void display() { //displays the list
System.out.println(this.data);
}
public void add(T integer) { // in this function we have added the <t> type object into the arraylist and called upheapify
data.add(integer);
upheapify(data.size() - 1);
}
private void upheapify(int ci) {
if (ci == 0) {
return;
}
int pi = (ci - 1) / 2;
if (isLarger(ci,pi) == true) {
swap(ci, pi);
upheapify(pi);
}
}
private boolean isLarger(int i, int j) {
T ith = data.get(i);
T jth = data.get(j);
if(ctor.compare(ith,jth)>0)
{
return true;
}
else
{
return false;
}
}
private void swap(int ci, int pi) { // swap function written like this because of the generic property
T ith = data.get(ci);
T jth=data.get(pi);
data.set(ci, jth);
data.set(pi, ith);
}
public T getHP() {
return data.get(0);
}
public T removeHP() {
swap(0, data.size() - 1);
T rv=data.remove(data.size()-1);
downheapify(0);
return rv;
}
private void downheapify(int pi) {
int lci = 2 * pi + 1;
int rci = 2 * pi + 2;
int max = pi;
if (lci < data.size() && isLarger(lci, max) == true) {
max = lci;
}
if (rci < data.size() && isLarger(rci, max) == true) {
max = rci;
}
if (max != pi) {
swap(pi, max);
downheapify(max);
}
}
}