Implement a PriorityQueue using a BinarySearchTree : Java

Question

I need to "create a priority queue implemented by a binary search tree (BST)" for my algorithms II class. However, I'm not sure exactly how you would use a binary search tree as a priority queue. Could someone clarify what it is that the assignment is asking me to do?

As a reference, here are the methods the PriorityQueue must implement:

add – adds a new item to the queue
peek – returns the head of the queue
remove – removes the head of the queue and returns it
search – returns the position of an element in the queue, or -1 if it is not found.
size – returns the total number of elements in the queue
inorder – returns an in-order, comma-separated string of every element in the queue
preorder – returns an pre-order, comma-separated string of every element in the queue
height – returns the height of the underlying BST

Thank you in advance for any advice!!

Answer 1

A Binary Search Tree is always ordered and will always stay in order if new items are inserted.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

And that's your Priority Queue. In a possible implementation, items with least priority will get the highest number and items with the highest priority will get the lowest number. If these items are inserted into the BST and you read it inorder, then you have the order in which the queue should be processed.

To process the queue, you "pop" off the first element in the tree and the rest will be ordered automatically by the BST.

The only thing you have to take care about is the correct insertion of new elements into the tree and what happens if the first one is removed.

Your methods would be mapped to the tree operations, add inserts a new item in the correct place and modify the tree if necessary, size for example gives back the size of the tree, inorder will traverse the tree.

Hope that made it a bit clearer.