A priority queue is a data structure and each element has a priority associated with it. The high priority served before with low priority. The priority queue key will be unique. The priority queue can be implemented using Unordered linked list, ordered linked list, Ordered array, and balanced Binary search tree.
Write a program to implement the priority queue.
Algorithm Explanation
Insert operation inserts the data dynamically into the queue with a priority level. Delete minimum operation find the minimum element from the queue and delete.
Heap is an internal data structure for storing the priority queue elements. The priority queue uses first in first out property (FIFO) with a priority level.
Priority queue makes sure, it remove highest priority node before the lowest priority node.
maxHeapify property validates the above property. Extract maximum function extracts the maximum value from the priority queue.
Source Code
package com.dsacode.DataStructre.priorityqueue;
import java.util.Arrays;
public class PriorityQueueImpl {
private Integer[] mArray;
private int mHeapSize;
public PriorityQueueImpl(int maxSize) {
mArray = new Integer[maxSize];
mHeapSize = 0;
}
int parentIndex(int i) {
return (i + 1) / 2 - 1;
}
int leftChildIndex(int i) {
return 2 * i + 1;
}
int rightChildIndex(int i) {
return 2 * i + 2;
}
void maxHeapify(int i) {
int leftChildIndex = leftChildIndex(i);
int rightChildIndex = rightChildIndex(i);
int largestElementIndex;
if (leftChildIndex < mHeapSize && mArray[leftChildIndex] > mArray[i]) {
largestElementIndex = leftChildIndex;
} else {
largestElementIndex = i;
}
if (rightChildIndex < mHeapSize
&& mArray[rightChildIndex] > mArray[largestElementIndex]) {
largestElementIndex = rightChildIndex;
}
if (largestElementIndex != i) {
int tmpValue = mArray[i];
mArray[i] = mArray[largestElementIndex];
mArray[largestElementIndex] = tmpValue;
maxHeapify(largestElementIndex);
}
}
void buildMaxHeap() {
int heapSize = mArray.length;
for (int i = heapSize / 2; i >= 0; i--) {
maxHeapify(i);
}
}
public int max() {
return mArray[0];
}
public int extractMax() {
int max = mArray[0];
mArray[0] = mArray[mHeapSize - 1];
mArray[mHeapSize - 1] = null;
mHeapSize--;
maxHeapify(0);
return max;
}
void increaseKey(int i, int newValue) throws Exception {
if (newValue < mArray[i]) {
throw new Exception("New value is smaller than current value");
}
mArray[i] = newValue;
while (i > 0 && mArray[parentIndex(i)] < mArray[i]) {
int tmpValue = mArray[parentIndex(i)];
mArray[parentIndex(i)] = mArray[i];
mArray[i] = tmpValue;
i = parentIndex(i);
}
}
public boolean insert(int value) {
if (mHeapSize < mArray.length) {
mHeapSize++;
mArray[mHeapSize - 1] = value;
try {
increaseKey(mHeapSize - 1, value);
} catch (Exception e) {
return false;
}
return true;
} else {
return false;
}
}
public int size() {
return mHeapSize;
}
public String toString() {
String string = "";
for (int i = 0; i < mHeapSize; i++) {
string += mArray[i] + " ";
}
return string;
}
public static void main(String[] args) {
Integer[] array = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
System.out.println("Array of items for insert Priority Queue: "
+ Arrays.toString(array));
PriorityQueueImpl heap = new PriorityQueueImpl(100);
for (int i : array) {
heap.insert(i);
}
System.out.println("Items from Priority Queue: " + heap.toString());
System.out
.print("Items from Priority Queue extracted using Max items: ");
int heapSize = heap.size();
for (int i = 0; i < heapSize; i++) {
System.out.print(heap.extractMax() + " ");
}
System.out.println();
}
}
Output
Array of items for insert Priority Queue: [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
Items from Priority Queue: 16 14 10 8 7 3 9 1 4 2
Items from Priority Queue extracted using Max items: 16 14 10 9 8 7 4 3 2 1
Source Explanation
Construct the priority queue using array length.
Insert the elements from the array to priority queue using insert operation.
Insert function inserts the value to the array and increases the key. The increase key function swaps the parent index with array element.
Print the priority queue items and iterate all the item from priority queue using extract max function and display the values.
Extract max function extracts the maximum element from the heap and heavily the heap.
