FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Heaps/MinPriorityQueue.java at master · pymmrd/Java · GitHub
pymmrd
/
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
/
MinPriorityQueue.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
125 lines (114 loc) · 3.4 KB
Breadcrumbs
Java
/
DataStructures
/
Heaps
/
MinPriorityQueue.java
Copy path
File metadata and controls
125 lines (114 loc) · 3.4 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
121
122
123
124
125
package
DataStructures
.
Heaps
;
/**
* Minimum Priority Queue It is a part of heap data structure A heap is a specific tree based data
* structure in which all the nodes of tree are in a specific order. that is the children are
* arranged in some respect of their parents, can either be greater or less than the parent. This
* makes it a min priority queue or max priority queue.
*
* <p>
*
* <p>Functions: insert, delete, peek, isEmpty, print, heapSort, sink
*/
public
class
MinPriorityQueue
{
private
int
[]
heap
;
private
int
capacity
;
private
int
size
;
// calss the constructor and initializes the capacity
MinPriorityQueue
(
int
c
) {
this
.
capacity
=
c
;
this
.
size
=
0
;
this
.
heap
=
new
int
[
c
+
1
];
}
// inserts the key at the end and rearranges it
// so that the binary heap is in appropriate order
public
void
insert
(
int
key
) {
if
(
this
.
isFull
())
return
;
this
.
heap
[
this
.
size
+
1
] =
key
;
int
k
=
this
.
size
+
1
;
while
(
k
>
1
) {
if
(
this
.
heap
[
k
] <
this
.
heap
[
k
/
2
]) {
int
temp
=
this
.
heap
[
k
];
this
.
heap
[
k
] =
this
.
heap
[
k
/
2
];
this
.
heap
[
k
/
2
] =
temp
;
}
k
=
k
/
2
;
}
this
.
size
++;
}
// returns the highest priority value
public
int
peek
() {
return
this
.
heap
[
1
];
}
// returns boolean value whether the heap is empty or not
public
boolean
isEmpty
() {
if
(
0
==
this
.
size
)
return
true
;
return
false
;
}
// returns boolean value whether the heap is full or not
public
boolean
isFull
() {
if
(
this
.
size
==
this
.
capacity
)
return
true
;
return
false
;
}
// prints the heap
public
void
print
() {
for
(
int
i
=
1
;
i
<=
this
.
capacity
;
i
++)
System
.
out
.
print
(
this
.
heap
[
i
] +
" "
);
System
.
out
.
println
();
}
// heap sorting can be done by performing
// delete function to the number of times of the size of the heap
// it returns reverse sort because it is a min priority queue
public
void
heapSort
() {
for
(
int
i
=
1
;
i
<
this
.
capacity
;
i
++)
this
.
delete
();
}
// this function reorders the heap after every delete function
private
void
sink
() {
int
k
=
1
;
while
(
2
*
k
<=
this
.
size
||
2
*
k
+
1
<=
this
.
size
) {
int
minIndex
;
if
(
this
.
heap
[
2
*
k
] >=
this
.
heap
[
k
]) {
if
(
2
*
k
+
1
<=
this
.
size
&&
this
.
heap
[
2
*
k
+
1
] >=
this
.
heap
[
k
]) {
break
;
}
else
if
(
2
*
k
+
1
>
this
.
size
) {
break
;
}
}
if
(
2
*
k
+
1
>
this
.
size
) {
minIndex
=
this
.
heap
[
2
*
k
] <
this
.
heap
[
k
] ?
2
*
k
:
k
;
}
else
{
if
(
this
.
heap
[
k
] >
this
.
heap
[
2
*
k
] ||
this
.
heap
[
k
] >
this
.
heap
[
2
*
k
+
1
]) {
minIndex
=
this
.
heap
[
2
*
k
] <
this
.
heap
[
2
*
k
+
1
] ?
2
*
k
:
2
*
k
+
1
;
}
else
{
minIndex
=
k
;
}
}
int
temp
=
this
.
heap
[
k
];
this
.
heap
[
k
] =
this
.
heap
[
minIndex
];
this
.
heap
[
minIndex
] =
temp
;
k
=
minIndex
;
}
}
// deletes the highest priority value from the heap
public
int
delete
() {
int
min
=
this
.
heap
[
1
];
this
.
heap
[
1
] =
this
.
heap
[
this
.
size
];
this
.
heap
[
this
.
size
] =
min
;
this
.
size
--;
this
.
sink
();
return
min
;
}
public
static
void
main
(
String
[]
args
) {
// testing
MinPriorityQueue
q
=
new
MinPriorityQueue
(
8
);
q
.
insert
(
5
);
q
.
insert
(
2
);
q
.
insert
(
4
);
q
.
insert
(
1
);
q
.
insert
(
7
);
q
.
insert
(
6
);
q
.
insert
(
3
);
q
.
insert
(
8
);
q
.
print
();
// [ 1, 2, 3, 5, 7, 6, 4, 8 ]
q
.
heapSort
();
q
.
print
();
// [ 8, 7, 6, 5, 4, 3, 2, 1 ]
}
}
Back
|
FazBrowse Home
|
New Git URL