max-heap에서 n 번째로 큰 키의 위치에 대한 하한을 생각하려고 시도합니다. 힙이 배열되어 있다고 가정합니다. 상한의 최소값 (2^n-2, 배열 크기 -1)은 생각합니다. 그러나 항상 0으로 제한됩니다.힙 데이터 구조
문제의
Q
힙 데이터 구조
4
A
답변
0
초기 조사
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 개의 요소를 포함한다 (도 3 : 14 개 요소 일례 힙보고 6 위치에있는 값의 범위를 결정하려면 다음
는 그룹은 1)
따라서 하한은 3 (그룹 1의 요소 수 + 1)이고 상한은 11 (그룹 1의 요소 수 + 그룹 3의 요소 수 + 1)입니다.
+0
작성한 공식을 이해합니다. 아직도 하한을 얻지 못하고있다. n = 13에 대해 하한이 6 인 이유를 예제로 설명 할 수 있습니까? – turmoil
최대 힙의 경우 모든 노드 부모가 자신보다 크거나 같아야 만합니다. 루트 요소가 항상 힙의 다른 요소보다 크거나 같음을 의미합니다 ([부모]> = a [i], 여기서 i는 루트 노드가 아닙니다). 힙이 약하게 정렬되어 있으므로 최대 힙을 사용하는 경우 최대 (최대)를 얻을 수 있고 최소 힙에서는 최소 (최소) 만 얻을 수 있음을 기억하십시오. –