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. |