对于二进制堆优先级队列，有多少块外部存储器无法访问？

Question

我正在研究使用二进制堆作为内部数据结构的优先级队列。考虑到块大小为M的外部存储器模型，幻灯片声称deleteMin需要大约2log(n/M)块访问。

这是为什么？在原始论文中描述自下而上的启发式（Wegener 93）或幻灯片中找不到解释。

第一个块包含堆的根目录和第一个日志（M）级别。之后，对于每个节点，它必须读取每层的一个块，其将包含两个连续的子节点。只有在极少数情况下（因此“近似”）才需要读取两个块才能获取节点的两个子节点。由于第一个日志（M）级别将通过单个块访问进行读取，因此只需加载最低级别的(log n - log M) = log n/M级别的块。

2从哪里来？它将不得不在缓存逐出时将这些数据块写回磁盘，但通常不会在负载情况下进行解释吗？

我希望我已经很好地解释了这个问题。非常感谢！

Answer 1

您的分析对我来说似乎是正确的。没有必要为2。

顺便说一下，通常外部存储器算法使用M作为内存大小和B作为块大小。所以它会是log(n/B)块访问（只要M>2B左右）。