-
Notifications
You must be signed in to change notification settings - Fork 0
/
Heap
106 lines (77 loc) · 1.73 KB
/
Heap
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
94
95
96
97
98
99
100
101
102
103
104
105
106
//heapify
package world;
import java.util.ArrayList;
public class heap {
static void heapify(ArrayList<Integer> he,int i) {
int size=he.size();
int largest=i;
int left=2*i+1;
int right=2*i+2;
if(left<size && he.get(left)>he.get(largest)) {
largest=left;
}
if(right<size && he.get(right)>he.get(largest)) {
largest=right;
}
if(largest!=i) {
int temp=he.get(largest);
he.set(largest, he.get(i));
he.set(i,temp);
heapify(he,largest);
}
}
//insertion
void insert(ArrayList<Integer> he,int num) {
int size=he.size();
if(size==0) {
he.add(num);
}
else {
he.add(num);
for(int i=size/2-1;i>=0;i--) {
heapify(he,i);
}
}
}
//deletion
void delete(ArrayList<Integer> he,int num) {
int size=he.size();
int i;
for(i=0;i<size;i++) {
if(num==he.get(i)) {
break;
}
}
int temp=he.get(i);
he.set(i, he.get(size-1));
he.set(size-1,temp);
he.remove(size-1);
for(int j=size/2-1;j>=0;j--) {
heapify(he,j);
}
}
//print-heap
void print(ArrayList<Integer> res,int size) {
for(Integer i:res) {
System.out.print(i+"->");
}
System.out.println();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Integer> res=new ArrayList<Integer>();
int size=res.size();
heap h=new heap();
h.insert(res,3);
h.insert(res,4);
h.insert(res,6);
h.insert(res,2);
h.insert(res,9);
h.insert(res,1);
System.out.println("heap after insertion ");
h.print(res, size);
h.delete(res,4);
System.out.println("heap after Deletion ");
h.print(res, size);
}
}