FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm/PuzzleCoding/src/MinHeap.java at master · wodgithub/algorithm · GitHub
wodgithub
algorithm
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
MinHeap.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
120 lines (103 loc) · 3.17 KB
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
MinHeap.java
Copy path
File metadata and controls
120 lines (103 loc) · 3.17 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/**
* http://algs4.cs.princeton.edu/24pq/
* min heap: only keep the min at the top, parent(root) < left and right node
*/
public
class
MinHeap
{
private
int
maxSize
;
private
int
current
;
private
int
[]
heap
;
public
MinHeap
(
int
max
) {
maxSize
=
max
;
heap
=
new
int
[
maxSize
+
1
];
// min is heap[1], it easy to calculate left/right
current
=
0
;
// current index
}
public
void
insert
(
int
value
) {
if
(
current
==
maxSize
) {
throw
new
RuntimeException
(
"Heap is full!"
);
}
heap
[++
current
] =
value
;
// start from 1
shiftUp
(
current
);
}
public
boolean
isEmpty
() {
return
current
==
0
;
}
public
int
min
() {
if
(
isEmpty
())
throw
new
RuntimeException
(
"heap is empty"
);
return
heap
[
1
];
}
public
int
removeMin
() {
if
(
isEmpty
())
throw
new
RuntimeException
(
"heap is empty"
);
int
min
=
heap
[
1
];
swap
(
1
,
current
);
// heap[current] = Integer.MAX_VALUE;
current
--;
if
(
current
!=
0
)
shiftDown
(
1
);
return
min
;
}
private
void
shiftUp
(
int
k
) {
// k/2 is parent, parent < left/right
while
(
k
>
1
&&
heap
[
k
/
2
] >
heap
[
k
]) {
swap
(
k
/
2
,
k
);
k
=
k
/
2
;
}
}
private
void
shiftDown
(
int
k
) {
while
(
2
*
k
<=
current
) {
int
i
=
2
*
k
;
// left child
int
j
=
i
+
1
;
// right child
//find the smallest of left and right
if
(
i
<
current
&&
heap
[
i
] >
heap
[
j
]) {
i
++;
// i = j
}
if
(
heap
[
k
] <
heap
[
i
]) {
break
;
}
swap
(
k
,
i
);
k
=
i
;
}
}
private
void
swap
(
int
i
,
int
j
) {
int
tmp
=
heap
[
i
];
heap
[
i
] =
heap
[
j
];
heap
[
j
] =
tmp
;
}
// is pq[1..N] a min heap?
private
boolean
isMinHeap
() {
return
isMinHeap
(
1
);
}
// is subtree of pq[1..N] rooted at k a min heap?
private
boolean
isMinHeap
(
int
k
) {
if
(
k
>
current
)
return
true
;
int
left
=
2
*
k
,
right
=
2
*
k
+
1
;
if
(
left
<=
current
&&
heap
[
k
] >
heap
[
left
])
return
false
;
if
(
right
<=
current
&&
heap
[
k
] >
heap
[
right
])
return
false
;
return
isMinHeap
(
left
) &&
isMinHeap
(
right
);
}
public
void
printHeap
() {
System
.
out
.
print
(
"heap: "
);
for
(
int
i
=
1
;
i
<=
current
;
i
++) {
System
.
out
.
print
(
heap
[
i
] +
" "
);
}
System
.
out
.
println
();
}
public
static
void
main
(
String
[]
args
) {
int
[]
a
=
new
int
[]{
5
,
3
,
4
,
1
,
0
,
6
,
7
,
2
};
MinHeap
minHeap
=
new
MinHeap
(
a
.
length
);
for
(
int
i
=
0
;
i
<
a
.
length
;
i
++) {
minHeap
.
insert
(
a
[
i
]);
}
System
.
out
.
println
(
minHeap
.
isMinHeap
());
minHeap
.
printHeap
();
System
.
out
.
println
(
minHeap
.
removeMin
());
System
.
out
.
println
(
minHeap
.
removeMin
());
System
.
out
.
println
(
minHeap
.
isMinHeap
());
minHeap
.
printHeap
();
System
.
out
.
println
(
minHeap
.
removeMin
());
System
.
out
.
println
(
minHeap
.
removeMin
());
System
.
out
.
println
(
minHeap
.
removeMin
());
minHeap
.
printHeap
();
}
}
Back
|
FazBrowse Home
|
New Git URL