Implementing PriorityQueue Using BinarySearchTree: Java

Question

I need to "create a priority queue implemented by the binary search tree (BST)" for my class II algorithms. However, I do not know exactly how to use the binary search tree as a priority queue. Can someone clarify what exactly the request is asking me?

As reference, the methods that PriorityQueue should implement are given:

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 The binary search tree is always ordered and will always remain in order if new elements are inserted.

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

And it is your turn of priorities. In a possible implementation, the elements with the lowest priority will receive the highest number, and the highest priorities will receive the lowest number. If these elements 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” the first item in the tree, and the rest will be automatically ordered by BST.

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

Your methods will be mapped to the tree, add inserts a new element in the right place and if necessary modifies the tree, for example, size returns the size of the tree, inorder will cross the tree.

Hope this made it clearer.

Answer 2

A binary search tree is used to efficiently serve items in sorted order. If the sort order is based on priority, your binary tree becomes a priority queue. You delete the item with the highest priority and insert new items according to their priority.

Edited to add:

This may help consider alternatives - if you used a linked list as your turn, how do you know where to insert a new item, except go all the way down the list, which is O (N) with the worst case N. Using a binary tree solves this a problem.

Answer 3

add peek remove - standard methods for BST

for search, you can cache the size in each node, which will be the current number of elements in the subtree of which node is the root (or in other words node.size = 1+ (node.right==null?0:node.right.size) + (node.left==null?0:node.left.size) )

then the search will be

 int search(E el,Node n){ if(n==null)return -1;//stop recursion && nullpointer int comp = el.compareTo(n.value); if(comp==0)return n.left==null?0:node.left.size; else if(comp<0){ return search(el,node.left); }else{ int res = search(el,node.right) return res<0?res:res+(n.left==null?0:node.left.size)+1;//pass through -1 unmodified } }