힙 데이터 구조

Question

max-heap에서 n 번째로 큰 키의 위치에 대한 하한을 생각하려고 시도합니다. 힙이 배열되어 있다고 가정합니다. 상한의 최소값 (2^n-2, 배열 크기 -1)은 생각합니다. 그러나 항상 0으로 제한됩니다.

문제의

Answer 1

초기 조사

n lb up 
1 1 1 
2 2 3 
3 2 7 
4 2 14 
9 3 14 
10 4 14 
12 5 14 
13 6 14 
14 8 14 

댄 큰 가능 요소의 수를 결정하기 위해 (힙 14 개 개의 요소가 가정) n 및 상한 및 하한 사이의 관계식을 계시 요소를 힙 배열의 특정 위치에두면 해당 위치를 루트로하는 하위 트리의 크기가 계산됩니다. 계산 거꾸로 수행되도록 주 :이 두 숫자는 다음 식

# of elements possible larger = total number of elements - size of subtree - 1 

EDIT 의해 관련되어있다. 배열/힙의 위치가 주어지면 힙이 정렬 된 경우 값의 위치를 ​​결정할 수 있습니다. 현재 요소보다 크게 보장

1. 요소 (부모, 부모의 부모, ...)을 보장받을 수 있습니다
2. 요소 : 세 개의 파티션으로 힙이 분할 될 수있다 노드를 감안할 때 현재 요소 (현재 요소를 루틴으로하는 하위 트리)보다 작음
3. 나머지 요소는 현재 요소보다 크거나 작을 수 있습니다.
   • 그룹 1 개의 요소를 포함한다 (도 3 : 14 개 요소 일례 힙보고 6 위치에있는 값의 범위를 결정하려면 다음

는 그룹은 1)

그룹 2는 두 개의 요소 (12,13)를 포함합니다.

그룹 3에는 나머지 9 개의 요소 (현재 값 제외) (2, 4, 5, 7, 8, 9, 10, 11, 14)

따라서 하한은 3 (그룹 1의 요소 수 + 1)이고 상한은 11 (그룹 1의 요소 수 + 그룹 3의 요소 수 + 1)입니다.