Implement a Priority Queue data structure
Must have methods for:
- Offer (Add element to the queue)
- Peek (Retrieves the root of the queue)
- Poll (Retrieves and removes the root of the queue)
- Size (Returns the number of elements in the queue)
Solutions (Click to expand)
We will create class that acts as a wrapper for an array list.
Size:
size() will return the current length of the list
Peek:
peek() will return the first element of the list. If the list is empty the method will return null/undefined
Poll:
poll() will "pop" the first element of the list and swap it with the last. The last element will be removed from the list. We will then call heapifyDown(). For as long as there is a left child (calculated by i * 2 + 1) we will compare the values of the left and right child (if it exists) and get the smaller of the two. The parent element will be swapped with the smaller of the two children and the operation will continue down the tree. If the parent is smaller than the smallest of the two, the parent is in the right place and we can end the operation.
Offer:
offer(element) will push given element to the end of the list and heapifyUp() will be called. The elements will be compared with its parent (calculated by (i - 1) / 2 Math.floor to truncate with JavaScript). If the current element is smaller than its parent the two will swap. The operations will continue we reach the root or the parent element is smaller than the current element.