Skip to content

Commit 5512fea

Browse files
puneetripathipuneetripathi
authored
Improve priority queues with max-heap (TheAlgorithms#3648)
1 parent 8ba295b commit 5512fea

1 file changed

Lines changed: 90 additions & 40 deletions

File tree

‎src/main/java/com/thealgorithms/datastructures/queues/PriorityQueues.java‎

Lines changed: 90 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
11
package com.thealgorithms.datastructures.queues;
22

3+
4+
5+
36
/**
47
* This class implements a PriorityQueue.
58
*
@@ -8,6 +11,8 @@
811
* most important elements are placed at the front/on the top. In this example I
912
* give numbers that are bigger, a higher priority. Queues in theory have no
1013
* fixed size but when using an array implementation it does.
14+
* <p>
15+
* Additional contibutions made by: PuneetTri(https://github.com/PuneetTri)
1116
*/
1217
class PriorityQueue {
1318

@@ -25,42 +30,113 @@ class PriorityQueue {
2530
private int nItems;
2631

2732
/**
28-
* Constructor
33+
* Default Constructor
34+
*/
35+
36+
public PriorityQueue() {
37+
/* If capacity is not defined, default size of 11 would be used
38+
* capacity=max+1 because we cant access 0th element of PQ, and to
39+
* accomodate (max)th elements we need capacity to be max+1.
40+
* Parent is at position k, child at position (k*2,k*2+1), if we
41+
* use position 0 in our queue, its child would be at:
42+
* (0*2, 0*2+1) -> (0,0). This is why we start at position 1
43+
*/
44+
int size = 11; // Default value of 11
45+
maxSize = size + 1;
46+
queueArray = new int[maxSize];
47+
nItems = 0;
48+
}
49+
50+
/**
51+
* Parameterized Constructor
2952
*
3053
* @param size Size of the queue
3154
*/
55+
3256
public PriorityQueue(int size) {
33-
maxSize = size;
34-
queueArray = new int[size];
57+
maxSize = size + 1;
58+
queueArray = new int[maxSize];
3559
nItems = 0;
3660
}
3761

62+
/**
63+
* Helper function for the max-heap implementation of PQ
64+
* Function would help demote parent node to their correct
65+
* position
66+
*
67+
* @param pos Position of newly added element at bottom
68+
*/
69+
private void swim(int pos) {
70+
// Check if parent is smaller than child node
71+
while (pos > 1 && (queueArray[pos / 2] < queueArray[pos])) {
72+
// In such case swap value of child with parent
73+
int temp = queueArray[pos];
74+
queueArray[pos] = queueArray[pos / 2];
75+
queueArray[pos / 2] = temp;
76+
pos = pos / 2; // Jump to position of parent node
77+
}
78+
// Promotion of child node will go on until it becomes smaller than the parent
79+
}
80+
81+
/**
82+
* Helper function for the max-heap implementation of PQ
83+
* Function would help demote parent node to their correct
84+
* position
85+
*
86+
* @param pos Position of element at top
87+
*/
88+
private void sink(int pos) {
89+
// Check if node's position is that of parent node
90+
while (2 * pos <= nItems) {
91+
int current = 2 * pos; // Jump to the positon of child node
92+
// Compare both the children for the greater one
93+
if (current < nItems && queueArray[current] < queueArray[current + 1]) current++;
94+
// If the parent node is greater, sink operation is complete. Break the loop
95+
if (queueArray[pos] >= queueArray[current]) break;
96+
97+
// If not exchange the value of parent with child
98+
int temp = queueArray[pos];
99+
queueArray[pos] = queueArray[current];
100+
queueArray[current] = temp;
101+
pos = current; // Exchange parent position to child position in the array
102+
}
103+
}
104+
38105
/**
39106
* Inserts an element in it's appropriate place
40107
*
41108
* @param value Value to be inserted
42109
*/
43110
public void insert(int value) {
111+
// Print overflow message if the capacity is full
44112
if (isFull()) {
45113
throw new RuntimeException("Queue is full");
46114
} else {
47-
int j = nItems - 1; // index of last element
48-
while (j >= 0 && queueArray[j] > value) {
49-
queueArray[j + 1] = queueArray[j]; // Shifts every element up to make room for insertion
50-
j--;
51-
}
52-
queueArray[j + 1] = value; // Once the correct position is found the value is inserted
53-
nItems++;
115+
queueArray[++nItems] = value;
116+
swim(nItems); // Swim up the element to its correct position
54117
}
55118
}
56119

57120
/**
58-
* Remove the element from the front of the queue
121+
* Dequeue the element with the max priority from PQ
59122
*
60123
* @return The element removed
61124
*/
62125
public int remove() {
63-
return queueArray[--nItems];
126+
if (isEmpty()) {
127+
throw new RuntimeException("Queue is Empty");
128+
} else {
129+
int max = queueArray[1]; // By defintion of our max-heap, value at queueArray[1] pos is the greatest
130+
131+
// Swap max and last element
132+
int temp = queueArray[1];
133+
queueArray[1] = queueArray[nItems];
134+
queueArray[nItems] = temp;
135+
queueArray[nItems--] = 0; // Nullify the last element from the priority queue
136+
sink(1); // Sink the element in order
137+
138+
return max;
139+
}
64140
}
65141

66142
/**
@@ -69,7 +145,7 @@ public int remove() {
69145
* @return element at the front of the queue
70146
*/
71147
public int peek() {
72-
return queueArray[nItems - 1];
148+
return queueArray[1];
73149
}
74150

75151
/**
@@ -87,7 +163,7 @@ public boolean isEmpty() {
87163
* @return true if the queue is full
88164
*/
89165
public boolean isFull() {
90-
return (nItems == maxSize);
166+
return (nItems == maxSize - 1);
91167
}
92168

93169
/**
@@ -100,29 +176,3 @@ public int getSize() {
100176
}
101177
}
102178

103-
/**
104-
* This class implements the PriorityQueue class above.
105-
*
106-
* @author Unknown
107-
*/
108-
public class PriorityQueues {
109-
110-
/**
111-
* Main method
112-
*
113-
* @param args Command Line Arguments
114-
*/
115-
public static void main(String[] args) {
116-
PriorityQueue myQueue = new PriorityQueue(4);
117-
myQueue.insert(10);
118-
myQueue.insert(2);
119-
myQueue.insert(5);
120-
myQueue.insert(3);
121-
// [2, 3, 5, 10] Here higher numbers have higher priority, so they are on the top
122-
123-
for (int i = 3; i >= 0; i--) {
124-
System.out.print(myQueue.remove() + " "); // will print the queue in reverse order [10, 5, 3, 2]
125-
}
126-
// As you can see, a Priority Queue can be used as a sorting algotithm
127-
}
128-
}

0 commit comments

Comments
 (0)