使用BinarySearchTree实现PriorityQueue：C++

-2

我必须创建一个项目：在二叉搜索树中表示的优先级队列。这是我的算法类。我不确定如何使用二叉搜索树作为优先级队列。我在互联网上找到的所有例子都是关于堆，而且“永远不应该在bst中实施优先队列，而只是在堆中”。有人可以向我解释我应该怎么做？谢谢！使用BinarySearchTree实现PriorityQueue：C++

来源

2017-06-29 Ciprian

如果你的任务已经有这么多麻烦，你应该和你的教授或他们的助手讨论。 –

通过确保所有节点一直遵守heap属性（节点的值不大于任何子节点的值），可以在*二叉树*中实现优先级队列（注意* search *的故意缺失）。这种方法实际上适用于任意形状的树。对于堆而言，树是否使用树节点或数组中的隐式树来表示并不重要。 –

作为一个提示，优先级队列需要有效支持插入元素，读取最小值（或最大值，在最大优先级队列中），并删除最小值。 BST已经支持快速插入和删除。因此，如果您将优先级队列中的所有元素存储在BST中，您会如何找到最小值？看看你是否可以使用这样一个事实，即BST按排序顺序存储它的元素，以找到找到最小值的非常快的算法。

来源

2017-06-29 20:58:12 templatetypedef

使用BinarySearchTree实现PriorityQueue：C++

回答

相关问题