The priority queue is a data structure with each element has a priority associated with it. The high priority element served before low priority element.
Priority queues provide extra flexibility over sorting mechanism. Write a program to implement the priority queue.
source Code
package com.dsacode.Algorithm.sorting; import java.util.Arrays; public class PriorityQueue { private Integer[] mArray; private int mHeapSize; public PriorityQueue(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) { int[] arr={12,34,56,23,45,78,46}; System.out.println("unsorted array before sorting from Array : " + Arrays.toString(arr)); PriorityQueue heap = new PriorityQueue(100); for (int i : arr) { heap.insert(i); } System.out.println("unsorted array before sorting from Heap : " +heap.toString()); int heapSize = heap.size(); System.out.print("Sorted array after sorting from PriorityQueue : "); for (int i = 0; i < heapSize; i++) { System.out.print(heap.extractMax() + " "); } } }
Output
Unsorted array before sorting from Array: [12, 34, 56, 23, 45, 78, 46] Unsorted array before sorting from Heap: 78 45 56 12 23 34 46 Sorted array after sorting from Priority Queue: 78 56 46 45 34 23 12
Algorithm Explanation
![]() | Insert operation inserts an item into the priority queues based on the priority. |
![]() | Remove operation remove and return an item from the queue. The item removed with the highest priority. |
![]() | The MaxHeapify function takes an array A and its index i. It assumes, the left and right subtrees are already sorted. |
![]() | The procedure lets the value of A[i] float down in the max-heap so that the subtree rooted at index i becomes a max-heap. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
O(n log(n)) | O(n log(n)) | O(n log(n)) |