forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinPriorityQueue.java
More file actions
133 lines (122 loc) · 3.88 KB
/
MinPriorityQueue.java
File metadata and controls
133 lines (122 loc) · 3.88 KB
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 ]
}
}