java - 使用 BinarySearchTree : Java 实现 PriorityQueue

Question

我需要为我的算法 II 类(class)“创建一个由二叉搜索树 (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

提前感谢您的任何建议!!

Answer 1

A Binary Search Tree总是有序的，如果插入新项目，将始终保持有序。

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.

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

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

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

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

希望这能让它更清晰一些。