FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Heaps/MinPriorityQueue.java at master · java66liu/Java · GitHub
java66liu
/
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
133 lines (122 loc) · 3.88 KB
Breadcrumbs
Java
/
DataStructures
/
Heaps
/
MinPriorityQueue.java
Copy path
File metadata and controls
133 lines (122 loc) · 3.88 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
126
127
128
129
130
131
132
133
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