An ordinary queue is a first in first out data structure. Elements are added at the end of the queue and deleted from the queue head. In some cases, we may need to find the maximum or minimum value in the queue. For example, a queue is used to save computer tasks. Generally, computer tasks have priority. We need to find the task with the highest priority among these computer tasks to execute first. After execution, we need to remove this task from the queue. To complete this function, ordinary queues need to traverse all elements in the queue every time, compare and find the maximum value. The efficiency is not very high. At this time, we can use a special queue to complete this demand, priority queue.
According to their different functions, priority queues can be divided into the following two types:
- Maximum priority queue: you can get and delete the maximum value in the queue
- Minimum priority queue: the smallest value in the queue can be obtained and deleted
1 maximum priority queue
We have learned about heap before, and the heap structure can easily delete the maximum value. Therefore, next, we can realize the maximum priority queue based on the heap area.
1.1 API design of maximum priority queue
1.2 code implementation of maximum priority queue
/**
* Maximum priority queue
* Implementation with heap
*/
public class MaxPriorityQueue<T extends Comparable<T>> {
//Define an array to store elements in the heap
private T[] items;
//Number of elements in the storage heap
private int N;
//Constructor initialization parameters
public MaxPriorityQueue(int capacity) {
items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
//Number of elements in the queue
public int size() {
return N;
}
//Is the queue empty
public boolean isEmpty() {
return N == 0;
}
//Queue insert element
public void insert(T t) {
//Add elements at the maximum index and increment
items[++N] = t;
//Float the element up to the correct position
swim(N);
}
//The queue floats up after the element is inserted so that it is in the correct position
public void swim(int k) {
while (k > 1) {
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
//Delete the largest element and return this element
public T delMax() {
T max = items[1];
//Swap the position of the largest element and the last element
exch(1, N);
//Delete last element
items[N] = null;
N--;
//Sink element 1 to the correct position
sink(1);
return max;
}
//Sink after deleting elements
public void sink(int k) {
while (2 * k <= N) {
int max;
//If there are right child nodes
if (2 * k + 1 <= N) {
if (less(2 * k + 1, 2 * k)) {
max = 2 * k;
} else {
max = 2 * k + 1;
}
} else {
max = 2 * k;
}
if (!less(k, max)) {
break;
}
exch(k, max);
k = max;
}
}
//Compare element sizes
public boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
//Exchange element
public void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
public static void main(String[] args) {
//Create minimum priority queue object
MaxPriorityQueue<String> queue = new MaxPriorityQueue<>(10);
//Save data to queue
queue.insert("G");
queue.insert("F");
queue.insert("E");
queue.insert("D");
queue.insert("C");
queue.insert("B");
queue.insert("A");
//Get the elements in the minimum priority queue through a loop
while (!queue.isEmpty()) {
String min = queue.delMax();
System.out.print(min + " ");
}
}
}
2 minimum priority queue
The implementation of the minimum priority queue is also relatively simple. We can also complete the minimum priority queue based on the heap. When we studied the heap earlier, the arrays storing data elements in the heap should meet the following characteristics:
- The largest element is placed at index 1 of the array.
- The data of each node is always greater than or equal to the data of its two child nodes.
In fact, the heap we implemented before can be called the maximum heap. We can use the opposite idea to realize the minimum heap, so that the array storing data elements in the heap meets the following characteristics:
- The smallest element is placed at index 1 of the array.
- The data of each node is always less than or equal to the data of its two child nodes.
- In this way, we can quickly access the smallest data in the heap.
2.1 API design of minimum priority queue
2.2 code implementation of minimum priority queue
/**
* Minimum priority queue
* Implementation with heap
*/
public class MinPriorityQueue<T extends Comparable<T>> {
//Define an array to store elements in the heap
private T[] items;
//Record the number of elements in the heap
private int N;
//Constructor initialization parameters
public MinPriorityQueue(int capacity) {
items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
//Judge whether the queue is empty
public boolean isEmpty() {
return N == 0;
}
//Get the number of elements in the queue
public int size() {
return N;
}
//Insert elements (insert elements at the maximum index and float up to adjust the order)
public void insert(T t) {
items[++N] = t;
//Float up
swim(N);
}
//Floating up operation after inserting an element, so that the inserted k element is in another correct position in the heap
public void swim(int k) {
//Comparison between k and its parent node k/2
while (k > 1) {
if (less(k, k / 2)) {
exch(k, k / 2);
}
k = k / 2;
}
}
//Delete maximum element
public T delMin() {
//Take out the largest element with index 1
T minT = items[1];
//Swap maximum index and 1 element
exch(1, N);
//Delete element at maximum index
items[N] = null;
//Element decrement
N--;
//Now drop the element with index 1 and adjust it to the correct position
sink(1);
return minT;
}
//Sink after deleting the largest element (the last element is exchanged with the first element)
public void sink(int k) {
while (2 * k <= N) {
//Find the maximum value in the child node
//If there is a right child node
int min;
if (2 * k + 1 <= N) {
if (less(2 * k, 2 * k + 1)) {
min = 2 * k;
} else {
min = 2 * k + 1;
}
} else {
min = 2 * k;
}
//Interpret the current node and child node values
if (less(k, min)) {
break;
}
exch(k, min);
//The index points to the child node
k = min;
}
}
//Compare element sizes
public boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
//Swap element location
public void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
public static void main(String[] args) {
//Create minimum priority queue object
MinPriorityQueue<String> queue = new MinPriorityQueue<>(10);
//Save data to queue
queue.insert("G");
queue.insert("F");
queue.insert("E");
queue.insert("D");
queue.insert("C");
queue.insert("B");
queue.insert("A");
//Get the elements in the minimum priority queue through a loop
while (!queue.isEmpty()) {
String min = queue.delMin();
System.out.print(min + " ");
}
}
}
3 index priority queue
In the previously implemented maximum priority queue and minimum priority queue, they can quickly access the maximum and minimum elements in the queue respectively, but they have a disadvantage that they have no way to access the objects that already exist in the priority queue through the index and update them. In order to achieve this goal, based on the priority queue, learn a new data structure, index the priority queue. Next, we take the minimum index priority queue as an example.
3.1 implementation idea of index priority queue
Step 1:
When storing data, associate each data element with an integer, such as insert (int, k, t, t). We can regard k as an integer associated with T. then our implementation needs to quickly obtain the T element in the queue through the value of k. at this time, the value of k needs to be unique.
The most intuitive idea is that we can use a T[] items array to save data elements. When inserting (int k, t t t), we can regard K as the index of the items array and put the T element at the index k of the items array. In this way, it is very convenient for us to obtain the T element according to K, and we can get the items[k] directly.
Step 2:
As a result of the completion of step 1, although we associate an integer with each element and can use this integer to quickly obtain the element, the order of the elements in the items array is random and not heap ordered. Therefore, in order to meet this requirement, we can add an array int[]pq to save the index of each element in the items array, The PQ array needs to be heap ordered, that is, the data elements items[pq[1]] corresponding to pq[1] should be less than or equal to the data elements items[pq[2]] and items[pq[3]] corresponding to pq[2] and pq[3].
Three steps:
Through the analysis in step 2, we can find that when we make heap adjustment through floating and sinking, we actually adjust the pq array. If you need to modify the elements in items, such as making items[0] = "H", it is obvious that we need to adjust the heap of the data in pq, and adjust the position of the elements in pq[9]. But now we will encounter a problem. What we modify is the value at the 0 index in the items array. How can we quickly know the position of the element in pq[9]? The most intuitive idea is to traverse the pq array and compare each element with 0. If the current element is 0, then adjust the element at the index, but the efficiency is very low. We can add another array, int[] qp, to store the reverse order of pq. For example: in pq array: pq[1]=6; Then, in the qp array, take 6 as the index and 1 as the value, and the result is: qp[6]=1;
After having pq array, if we modify items[0] = "H", we can first find the index of qp in qp array through index 0: qp[0]=9, and then adjust pq[9] directly.
3.2 API design of index priority queue
3.3 code implementation of minimum index priority queue
/**
* Minimum index priority queue
*/
public class IndexMinPriorityQueue<T extends Comparable<T>> {
//Elements in the storage heap
private T[] items;
//Save the index of each element in the items array. The pq array needs to be heap ordered
private int[] pq;
//Save the reverse order of pq, with pq value as index and pq index as value
private int[] qp;
//Record the number of elements in the heap
private int N;
//Constructor
public IndexMinPriorityQueue(int capacity) {
items = (T[]) new Comparable[capacity + 1];
pq = new int[capacity + 1];
qp = new int[capacity + 1];
this.N = 0;
//The default queue does not store elements
for (int i = 0; i < qp.length; i++) {
qp[i] = -1;
}
}
//Is the queue empty
public boolean isEmpty() {
return N == 0;
}
//Queue size
public int size() {
return N;
}
//Compare size
public boolean less(int i, int j) {
//Element size at pq index
return items[pq[i]].compareTo(items[pq[j]]) < 0;
}
//Exchange element order
public void exch(int i, int j) {
//Index order in exchange pq
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
//Update data in qp
qp[pq[i]] = i;
qp[pq[j]] = j;
}
//Judge whether the index at k already exists
public boolean contain(int k) {
return qp[k] != -1;
}
//Index associated with the smallest element
public int minIndex() {
return pq[1];
}
//Insert element t at index i
public void insert(int i, T t) {
if (contain(i)) {
return;
}
//Save the data to the i position corresponding to the items
items[i] = t;
//Number of elements plus 1
N++;
//Store i in pq
pq[N] = i;
//Reverse order in record qp
qp[i] = N;
//Complete reactor adjustment by floating up
swim(i);
}
//Delete minimum index
public int delMin() {
//Gets the index associated with the smallest element
int minIndex = pq[1];
//Swap elements at 1 and N at pq index
exch(1, N);
//Delete inverse index
qp[pq[N]] = -1;
//Delete index stored in pq
pq[N] = -1;
//Delete element
items[minIndex] = null;
N--;
//Sinking operation
sink(1);
return minIndex;
}
//Deletes the specified index
public void delete(int i) {
//i index at pq
int k = qp[i];
//Swap k and last element index
exch(k, N);
//Delete element
items[k] = null;
//Delete inverse index
qp[pq[N]] = -1;
//Delete the index
pq[N] = -1;
//Heap adjustment
sink(k);
swim(k);
}
//Change the element associated with index i to t
public void changeItem(int i, T t) {
//Modify the element at i position in the items array to t
int k = qp[i];
//Find where i appears in pq
items[k] = t;
//Adjustment reactor
swim(k);
sink(k);
}
//Float up
public void swim(int k) {
while (k > 1) {
if (less(k, k / 2)) {
exch(k, k / 2);
}
k = k / 2;
}
}
//sink
public void sink(int k) {
while (2 * k < N) {
//Find the smallest element index in the child node
int min;
//If there are right child nodes
if (2 * k + 1 < N) {
if (less(2 * k + 1, 2 * k)) {
min = 2 * k + 1;
} else {
min = 2 * k;
}
} else {
min = 2 * k;
}
//If it is larger than the child node, no swap is needed
if (!less(k, min)) {
break;
}
exch(k, min);
k = min;
}
}
public static void main(String[] args) {
//Create index minimum priority queue object
IndexMinPriorityQueue<String> queue = new IndexMinPriorityQueue<>(10);
//Add element to queue
queue.insert(0, "A");
queue.insert(1, "C");
queue.insert(2, "F");
//Test modification
queue.changeItem(2, "B");
//Test delete
while (!queue.isEmpty()) {
int index = queue.delMin();
System.out.print(index + " ");
}
}
}
3.4 implementation of maximum index priority queue
package com.bcl.algorithm.priority;
/**
* Index maximum priority queue
*/
public class IndexMaxPriorityQueue<T extends Comparable<T>> {
//Elements in the storage heap
private T[] items;
//Store items index value
private int[] pq;
//Store the reverse order of the indexes in pq. The value of pq is the index and the index is the value
private int[] qp;
//Storing data in heap
private int N;
//Constructor initialization parameters
public IndexMaxPriorityQueue(int capacity) {
items = (T[]) new Comparable[capacity + 1];
pq = new int[capacity + 1];
qp = new int[capacity + 1];
this.N = 0;
// for (int i : qp) {
// qp[i] = -1;
// }
//The default queue does not store elements
for (int i = 0; i < qp.length; i++) {
qp[i] = -1;
}
}
//Is the queue empty
public boolean isEmpty() {
return N == 0;
}
//Queue size
public int size() {
return N;
}
public boolean max(int i, int j) {
return items[pq[i]].compareTo(items[pq[j]]) > 0;
}
//Exchange element order
public void exch(int i, int j) {
//Index order in exchange pq
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
//Update data in qp
qp[pq[i]] = i;
qp[pq[j]] = j;
}
//Include corresponding index
public boolean contain(int i) {
return qp[i] != -1;
}
//Maximum index
public int maxIndex() {
return pq[1];
}
//Insert element at index i
public void insert(int i, T t) {
if (contain(i)) {
return;
}
//Insert element t at items
items[i] = t;
//Self increasing number
N++;
//pq add index mapping
pq[N] = i;
//qp increases in reverse order
qp[i] = N;
//Float up and adjust the reactor sequence
swim(N);
}
//Delete maximum index
public int delMaxIndex() {
//Maximum element index found
int maxIndex = pq[1];
//Exchange element
exch(1, N);
//Delete element
items[maxIndex] = null;
//Delete inverse index
qp[pq[N]] = -1;
//Delete index
pq[N] = -1;
//Element reduction
N--;
//Sinking adjustment reactor sequence
sink(1);
return maxIndex;
}
//Delete element at index i
public void delete(int i) {
//Find the position of index i in pq and adjust the order of pq
int k = qp[i];
//Swap element positions at k
exch(k, N);
//Delete element
items[k] = null;
qp[pq[N]] = -1;
//Delete elements in pq
pq[N] = -1;
//Heap adjustment sequence
sink(k);
swim(k);
}
//Modify the value at index i to t
public void changeItems(int i, T t) {
items[i] = t;
int k = qp[i];
swim(k);
sink(k);
}
//Adjust the stacking order
public void swim(int k) {
while (k > 1) {
if (max(k, k / 2)) {
exch(k, k / 2);
}
k = k / 2;
}
}
//Adjust the stacking sequence by sinking
public void sink(int k) {
while (2 * k <= N) {
//Maximum child node found
int max;
if (2 * k + 1 <= N) {
if (max(2 * k + 1, 2 * k)) {
max = 2 * k + 1;
} else {
max = 2 * k;
}
} else {
max = 2 * k;
}
if (max(k, max)) {
break;
}
exch(k, max);
k = max;
}
}
public static void main(String[] args) {
//Create index minimum priority queue object
IndexMaxPriorityQueue<String> queue = new IndexMaxPriorityQueue<>(10);
//Add element to queue
queue.insert(0, "A");
queue.insert(1, "C");
queue.insert(2, "F");
//Test modification
queue.changeItems(2, "B");
//Test delete
while (!queue.isEmpty()) {
int index = queue.delMaxIndex();
System.out.print(index + " ");
}
}
}