data-structures - 哪种数据结构适合这个现实世界的情况？

Question

现实世界的问题：

假设在一家银行，客户在柜台前获得服务。并且在柜台，他们根据顾客的服务时间服务。服务时间最短的顾客在服务时间比前一位顾客多的顾客之前得到服务。这意味着，计数器遵循第一种方法完成的最短工作。

我的工作：

现在我的工作是选择合适的数据结构来为计数器找到优化的解决方案。并广泛地证明数据结构的选择是合理的（2 页/200 字或接近它）。

试过：

所以根据我的观察，我认为 BFS 是适合这种情况的完美数据结构。但我不知道如何用点和解释来描述它。我必须广泛地解释它。

期待：

5-6分关于我为什么选择数据结构的例子。

标签： data-structuresheapbreadth-first-search

Answer 1

首先想想为什么不应该使用BFS？

因为你想用最短的工作时间为客户服务，所以你需要用最短的时间找到工作。如果您使用 BFS，每次您想要找到下一个要服务的客户时，您都将遍历所有节点。因此，这不是理想的解决方案。

你需要什么？

您需要一些算法/数据结构，以便在新客户到达或已为某些客户提供服务时有效地找到最短的工作，而无需遍历整个客户/工作列表。这可以使用堆（优先级队列）来完成，更具体地说Min-Heaps。

为什么是堆？

1. 堆中的插入时间为 O(logN)
2. 可以使用 O(logN) 时间复杂度提取最小/最大元素，而无需遍历堆中的每个节点。
3. 无论您执行什么操作（插入/提取），最小/最大元素始终分别位于最小堆/最大堆中的顶部节点。

希望这可以帮助。