FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Heaps/MinHeap.java at master · j2cms/Java · GitHub
j2cms
/
Java
Public
forked from
TheAlgorithms/Java
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
DataStructures
/
Heaps
/
MinHeap.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
114 lines (99 loc) · 4.51 KB
Breadcrumbs
Java
/
DataStructures
/
Heaps
/
MinHeap.java
Copy path
File metadata and controls
114 lines (99 loc) · 4.51 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
package
DataStructures
.
Heaps
;
import
java
.
util
.
ArrayList
;
import
java
.
util
.
List
;
/**
* Heap tree where a node's key is higher than or equal to its parent's and lower than or equal
* to its children's.
*
* @author Nicolas Renard
*/
public
class
MinHeap
implements
Heap
{
private
final
List
<
HeapElement
>
minHeap
;
public
MinHeap
(
List
<
HeapElement
>
listElements
) {
minHeap
=
new
ArrayList
<>();
for
(
HeapElement
heapElement
:
listElements
) {
if
(
heapElement
!=
null
)
insertElement
(
heapElement
);
else
System
.
out
.
println
(
"Null element. Not added to heap"
);
}
if
(
minHeap
.
size
() ==
0
)
System
.
out
.
println
(
"No element has been added, empty heap."
);
}
// Get the element at a given index. The key for the list is equal to index value - 1
public
HeapElement
getElement
(
int
elementIndex
) {
if
((
elementIndex
<=
0
) || (
elementIndex
>
minHeap
.
size
()))
throw
new
IndexOutOfBoundsException
(
"Index out of heap range"
);
return
minHeap
.
get
(
elementIndex
-
1
);
}
// Get the key of the element at a given index
private
double
getElementKey
(
int
elementIndex
) {
return
minHeap
.
get
(
elementIndex
-
1
).
getKey
();
}
// Swaps two elements in the heap
private
void
swap
(
int
index1
,
int
index2
) {
HeapElement
temporaryElement
=
minHeap
.
get
(
index1
-
1
);
minHeap
.
set
(
index1
-
1
,
minHeap
.
get
(
index2
-
1
));
minHeap
.
set
(
index2
-
1
,
temporaryElement
);
}
// Toggle an element up to its right place as long as its key is lower than its parent's
private
void
toggleUp
(
int
elementIndex
) {
double
key
=
minHeap
.
get
(
elementIndex
-
1
).
getKey
();
while
(
getElementKey
((
int
)
Math
.
floor
(
elementIndex
/
2
)) >
key
) {
swap
(
elementIndex
, (
int
)
Math
.
floor
(
elementIndex
/
2
));
elementIndex
= (
int
)
Math
.
floor
(
elementIndex
/
2
);
}
}
// Toggle an element down to its right place as long as its key is higher
// than any of its children's
private
void
toggleDown
(
int
elementIndex
) {
double
key
=
minHeap
.
get
(
elementIndex
-
1
).
getKey
();
boolean
wrongOrder
= (
key
>
getElementKey
(
elementIndex
*
2
)) || (
key
>
getElementKey
(
Math
.
min
(
elementIndex
*
2
,
minHeap
.
size
())));
while
((
2
*
elementIndex
<=
minHeap
.
size
()) &&
wrongOrder
) {
// Check whether it shall swap the element with its left child or its right one if any.
if
((
2
*
elementIndex
<
minHeap
.
size
()) && (
getElementKey
(
elementIndex
*
2
+
1
) <
getElementKey
(
elementIndex
*
2
))) {
swap
(
elementIndex
,
2
*
elementIndex
+
1
);
elementIndex
=
2
*
elementIndex
+
1
;
}
else
{
swap
(
elementIndex
,
2
*
elementIndex
);
elementIndex
=
2
*
elementIndex
;
}
wrongOrder
= (
key
>
getElementKey
(
elementIndex
*
2
)) || (
key
>
getElementKey
(
Math
.
min
(
elementIndex
*
2
,
minHeap
.
size
())));
}
}
private
HeapElement
extractMin
() {
HeapElement
result
=
minHeap
.
get
(
0
);
deleteElement
(
0
);
return
result
;
}
@
Override
public
void
insertElement
(
HeapElement
element
) {
minHeap
.
add
(
element
);
toggleUp
(
minHeap
.
size
());
}
@
Override
public
void
deleteElement
(
int
elementIndex
) {
if
(
minHeap
.
isEmpty
())
try
{
throw
new
EmptyHeapException
(
"Attempt to delete an element from an empty heap"
);
}
catch
(
EmptyHeapException
e
) {
e
.
printStackTrace
();
}
if
((
elementIndex
>
minHeap
.
size
()) || (
elementIndex
<=
0
))
throw
new
IndexOutOfBoundsException
(
"Index out of heap range"
);
// The last element in heap replaces the one to be deleted
minHeap
.
set
(
elementIndex
-
1
,
getElement
(
minHeap
.
size
()));
minHeap
.
remove
(
minHeap
.
size
());
// Shall the new element be moved up...
if
(
getElementKey
(
elementIndex
) <
getElementKey
((
int
)
Math
.
floor
(
elementIndex
/
2
)))
toggleUp
(
elementIndex
);
// ... or down ?
else
if
(((
2
*
elementIndex
<=
minHeap
.
size
()) && (
getElementKey
(
elementIndex
) >
getElementKey
(
elementIndex
*
2
))) ||
((
2
*
elementIndex
<
minHeap
.
size
()) && (
getElementKey
(
elementIndex
) >
getElementKey
(
elementIndex
*
2
))))
toggleDown
(
elementIndex
);
}
@
Override
public
HeapElement
getElement
()
throws
EmptyHeapException
{
try
{
return
extractMin
();
}
catch
(
Exception
e
) {
throw
new
EmptyHeapException
(
"Heap is empty. Error retrieving element"
);
}
}
}
Back
|
FazBrowse Home
|
New Git URL