我正在研究优先级队列，它使用二进制堆作为其内部数据结构。考虑到块大小为 M 的外部存储器模型，幻灯片声称 deleteMin 需要大约2log(n/M)块访问。
为什么是这样？我在描述自下而上启发式（Wegener 93）的原始论文中找不到解释，在幻灯片中也找不到。
第一个块包含堆的根和第一个 log(M) 级别。之后，对于每个节点，它必须在每个级别读取一个块，其中将包含两个连续的子节点。只有在极少数情况下（因此是“近似值”）它才必须读取两个块来获取节点的两个子节点。由于将使用单个块访问读取第一个 log(M) 级别，因此它只需加载最低(log n - log M) = log n/M级别的块。
从哪里来2？它必须在缓存驱逐时将块写回磁盘，但这通常不是与负载有关吗？
我希望我已经很好地解释了这个问题。非常感谢！