gpt4 book ai didi

c++ - 用于快速插入和删除的堆 O(log n)

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:17:30 27 4
gpt4 key购买 nike

<分区>

我正在尝试找到一种具有以下几个属性的算法:

  • 使用数组作为存储(缓存友好)。
  • 只存储无符号整数。
  • 没有关联的值。
  • 插入和删除第i项的时间顺序为O(log n)。
  • 保持结构稳定,以便在遍历时删除元素。
  • 单个项目的顺序和查找并不重要,Max 或 Min 也不重要。

针对此类问题有多种解决方案。一种非常常见的是红/黑树。我不喜欢树来解决这个问题,因为我必须在其他事情中使用动态内存(比如存储我不需要的指针和相关值)。

我想到的另一个选择是使用二进制堆。它旨在快速删除最小/最大元素,因此适用于优先级队列。在我的例子中,我需要一些允许删除堆中任意项目的扩展版本。是否可以在 log(n) 时间内进行删除。网上有人提到,如果你在数组中有位置,就是这样。但是我找不到证明这是正确的证据。另一件事是删除期间的稳定性。如果答案是否定的,您有什么建议?

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