使用 BinarySearchTree 实现 PriorityQueue：Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6084676/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implement a PriorityQueue using a BinarySearchTree : Java
提问by Chris V.
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?
我需要为我的算法 II 类“创建一个由二叉搜索树（BST）实现的优先级队列”。但是，我不确定您将如何使用二叉搜索树作为优先队列。有人可以澄清一下作业要求我做什么吗？
As a reference, here are the methods the PriorityQueue must implement:
作为参考，以下是 PriorityQueue 必须实现的方法：
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!!
预先感谢您的任何建议！！
回答by slhck
A Binary Search Treeis 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.
这就是您的优先队列。在一种可能的实现方式中，优先级最低的项将获得最高编号，而优先级最高的项将获得最低编号。如果这些项目被插入到 BST 中并且你阅读了它inorder，那么你就有了队列应该被处理的顺序。
To process the queue, you "pop" off the first element in the tree and the rest will be ordered automatically by the BST.
要处理队列，您“弹出”树中的第一个元素，其余元素将由 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, addinserts a new item in the correct place and modify the tree if necessary, sizefor example gives back the size of the tree, inorderwill traverse the tree.
您的方法将映射到树操作，add在正确的位置插入一个新项目并在必要时修改树，size例如返回树的大小，inorder将遍历树。
Hope that made it a bit clearer.
希望这让它更清楚一点。
回答by ratchet freak
add peek remove are standard methods for a BST
add peek remove 是 BST 的标准方法
for search you can cache the size in each node which will be the current number of elements in the subtree of which the node is the root of (or in other words node.size = 1+ (node.right==null?0:node.right.size) + (node.left==null?0:node.left.size))
对于搜索，您可以缓存每个节点中的大小，这将是该节点是其根（或换句话说node.size = 1+ (node.right==null?0:node.right.size) + (node.left==null?0:node.left.size)）的子树中的当前元素数
then search becomes
然后搜索变成
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
}
}
回答by DNA
A binary search treeis used to efficiently maintain items in sorted order. If the sort-order is based on priority, then your binary tree becomes a priority queue. You pop off the highest priority item , and insert new items according to their priority.
一个二叉搜索树来有效维护有序的项目。如果排序顺序是基于优先级的，那么你的二叉树就变成了一个优先级队列。您弹出最高优先级的项目，并根据其优先级插入新项目。
Edited to add:
编辑添加：
It may help to consider the alternatives - if you used a linked list as your queue, how would you know where to insert a new item, other than by walking all the way down the list, which is O(N) with a worst case of N. Using a binary tree solves that problem.
考虑替代方案可能会有所帮助 - 如果您使用链表作为队列，您如何知道在哪里插入新项目，而不是一直沿着列表走下去，最坏的情况是 O(N) N. 使用二叉树解决了这个问题。
