## Question

Implement a Priority Queue

Once you think that you’ve solved the problem, click below to see the solution.

*As always, remember that practicing coding interview questions is as much about how you practice as the question itself. Make sure that you give the question a solid go before skipping to the solution. Ideally if you have time, write out the solution first by hand and then only type it into your computer to verify your work once you've verified it manually. To learn more about how to practice, check out this blog post.*

## Solution

How was that problem? You can check out the solution in the video below.

Here is the source code for the solution shown in the video (Github):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
// Implements a priority queue using a max heap. The heap is of fixed size and // represented using an array. public class PriorityQueue { int[] heap; int size; // Constructor initializes instance variables public PriorityQueue(int maxSize) { heap = new int[maxSize]; size = 0; } // Push an element on to the queue public void push(int val) { // If the queue is full then throw an exception if (size == heap.length) throw new IllegalStateException(); // Put the value in the next available space in the queue int pos = size; heap[pos] = val; // While val is bigger than its parent, swap it with its parent while (pos > 0) { // Get the parent and compare the values int parent = (pos+1) / 2 - 1; if (heap[parent] > heap[pos]) break; swapIndices(parent, pos); pos = parent; } // We added an element so increment the size size++; } // Pop the max element from the queue public int pop() { // If the queue is empty, throw an exception if (size == 0) throw new IllegalStateException (); // The top of the heap is the first item in the array, so save it off // to the side so we don't lose it int toReturn = heap[0]; // Move the bottom item in the heap to the first position. We don't need // to remove it from the array because we have the size variable heap[0] = heap[size - 1]; size--; // Bubble down the top element to the right spot int pos = 0; // We're going to be swapping with the children and any pos >= size / 2 // doesn't have any children while (pos < size / 2) { int leftChild = pos * 2 + 1; int rightChild = leftChild + 1; // If the right child exists and is greater than the left child, // compare it to the current position if (rightChild < size && heap[leftChild] < heap[rightChild]) { // Only swap if the value is less than the child if (heap[pos] >= heap[rightChild]) break; swapIndices(pos, rightChild); pos = rightChild; } else { // Do the same comparison with the left child if (heap[pos] >= heap[leftChild]) break; swapIndices(pos, leftChild); pos = leftChild; } } return toReturn; } // Swap the values at the indices private void swapIndices(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } } |

Did you get the right answer to this coding interview question? Please share your thoughts in the comments below.