使用二叉搜索树实现优先队列：Java

Question

我需要为我的算法II课程“创建一个由二叉搜索树（BST）实现的优先队列”。然而，我不确定如何使用二叉搜索树作为优先队列。有人能澄清一下这个任务要求我做什么吗？

以下是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

非常感谢您提前的任何建议！！

- Chris V.

---

你的最左节点应该包含最小值元素。当你poll()/pop()队列时，删除该元素并重新平衡（如果需要）。添加只是普通添加。祝好运，并记住，重复项需要一些非平凡的处理。 - bestsss

Answer 1

一棵二叉搜索树总是有序的，如果插入新项，则始终保持有序。 二叉搜索树相比其他数据结构的主要优势在于排序算法和搜索算法（例如中序遍历）可以非常高效地执行。

这就是你的优先队列。在可能的实现中，具有最低优先级的项目将获得最高编号，而具有最高优先级的项目将获得最低编号。如果将这些项目插入BST并按inorder读取它，则您将得到应处理队列的顺序。

为了处理队列，您需要“弹出”树中的第一个元素，其余元素将由BST自动排序。

唯一需要注意的事情是正确地将新元素插入树中以及如果删除第一个元素会发生什么。

您的方法将映射到树操作，add将在正确位置插入新项，并在必要时修改树，例如size返回树的大小，inorder将遍历树。

希望这让问题更加清晰明了。

- slhck

Answer 2

一个二叉搜索树用来高效地维护有序的项目。如果排序顺序基于优先级，那么你的二叉树就成为了一个优先队列。您可以弹出最高优先级的项目，并根据其优先级插入新项目。

编辑以添加：

考虑替代方案可能会对您有所帮助-如果您将链接列表用作队列，则除了通过完整遍历整个列表来查找要插入的位置（这是O(N)的，最坏情况下为N）之外，您还能怎样知道新项目的插入位置？使用二叉树解决了这个问题。

- DNA

Answer 3

添加、查看、删除是二叉搜索树的标准方法。

对于搜索，您可以在每个节点中缓存大小，这将是该节点为根的子树中当前元素数量（或者换句话说，node.size = 1+ (node.right==null?0:node.right.size) + (node.left==null?0:node.left.size)）

然后搜索变成了：

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
    }
}

- ratchet freak