gpt4 book ai didi

algorithm - 在 O(1) 中实现 extract-min

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:02:20 26 4
gpt4 key购买 nike

<分区>

Possible Duplicate:
Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

我需要实现一个 FIFO 数据结构,其中 Enqueue、Dequeue 和 Extract-Min 的摊销成本为 O(1)。

我考虑过使用一个常规队列,该队列使用链接列表进行 O(1) 入队和出队,然后对于 Extract-Min,我将遍历数组以获取最小值并将其删除。不过,这样做的成本将是 O(n),并且不会将摊余成本变为 O(1)。

如有任何帮助或提示,我们将不胜感激。

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com