바이너리 힙 우선 순위 큐에 대한 deleteMin 액세스의 외부 메모리 블록 수는 몇 개입니까?

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 정도)입니다.