我正在研究优先级队列，它使用二进制堆作为它们的内部数据结构。考虑到 block 大小为 M 的外部存储器模型，幻灯片声称 deleteMin 需要大约 2log(n/M) block 访问。
这是为什么？我在描述自下而上启发式 (Wegener 93) 的原始论文和幻灯片中都找不到解释。
第一个 block 包含堆的根和第一个 log(M) 层。之后，对于每个节点，它必须在每个级别读取一个 block ，其中将包含两个连续的子节点。只有在极少数情况下(因此是“近似”)，它才必须读取两个 block 才能获取节点的两个子节点。由于将通过单 block 访问读取第一个 log(M) 级别，因此它只需加载最低 (log n - log M) = log n/M 级别的 block 。
2 来自哪里？它必须在缓存逐出时将 block 写回磁盘，但这通常不是与负载一起考虑的吗？
我希望我已经很好地解释了这个问题。非常感谢!
最佳答案
您的分析对我来说似乎是正确的。不需要 2。
顺便说一句，通常外部存储器算法使用M作为内存大小，B作为 block 大小。所以它将是 log(n/B) block 访问(只要 M>2B 左右)。
关于algorithm - 一个二叉堆优先级队列的 deleteMin 访问了多少外部内存块？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11994368/