Priority queues insert the largest key value at the front of the queue (max heap). Write a program to implement max heap priority queue.
source Code
package com.dsacode.Algorithm.sorting;
import java.util.Arrays;
public class MaxheapPriorityqueue {
private Integer[] mArray;
private int mHeapSize;
public MaxheapPriorityqueue(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));
MaxheapPriorityqueue heap = new MaxheapPriorityqueue(100);
for (int i : array) {
heap.insert(i);
}
System.out.println("Itmes from Priority Queue: " + heap.toString());
System.out
.print("Itmes 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] Itmes from Priority Queue: 16 14 10 8 7 3 9 1 4 2 Itmes from Priority Queue extracted using Max items: 16 14 10 9 8 7 4 3 2 1
Algorithm Explanation
 | Insert an item into priority queue based on the priority. |
| Let r is the data at the top of the heap and t is the node at the top of the heap. |
| Replace t with the node at the lowest, farthest right position. |
| Heapify the whole tree and return r. |