index du 3ème plus petit élément dans le tas max.

Question

Comment trouver les indices possibles du 3ème plus petit élément dans un tas maximum de 1 à n éléments distincts ? Je sais que le plus petit élément sera n'importe où dans la feuille. Le deuxième plus petit élément sera n'importe où entre n/2 et n pour n supérieur à 3. Mais je ne sais pas comment calculer le troisième plus petit élément. Des suggestions ?

Answer 1

Le troisième plus petit élément a au plus deux descendants, ce qui signifie que son ou ses enfants sont des feuilles, ou qu'il est une feuille. (Pour prouver cela, vous devez également prouver qu'il est impossible pour un élément avec un seul enfant d'avoir un non-feuille comme enfant. Facile mais fastidieux).

Les feuilles, comme vous le notez presque, ont des indices dans la gamme [floor(n/2)+1, n] . Si n/2 est un nombre entier, alors cet élément a exactement un enfant (qui est une feuille), donc en ajoutant cela, on obtient la plage d'indices qui pourrait contenir le deuxième plus grand élément.

Un élément dont le premier enfant est dans l'intervalle de la feuille. [floor(n/2)+1,n] a au plus deux enfants, et aucun enfant non feuilleté. Cette plage est contiguë à la plage [ceil(n/2),n], et l'union des deux plages fournit toutes les positions possibles pour le troisième élément le plus grand.

Le premier enfant de l'élément à i a un indice 2i donc le premier élément dont le premier enfant est au minimum floor(n/2)+1 es floor(n/4)+1 .

Ainsi, les indices possibles auxquels vous pourriez trouver le troisième élément le plus grand est la gamme : [floor(n/4)+1,n] .

---

Voici une autre approche. Prenez un élément à l'indice i . Ses enfants immédiats sont 2i y 2i+1 ; ses petits-enfants sont 4i, 4i+1, 4i+2, 4i+3 et, en général, ses descendants au niveau k son 2ki, 2ki+1, ..., 2ki + 2ki-1 En résumé, [2ki, ..., 2k(i+1)-1 ] . Ces plages ne se chevauchent évidemment pas (en effet, à moins que i es 1 ils ne sont même pas contigus). Ainsi, si i a au moins un descendant au niveau k il a également un ensemble complet de descendants pour tous les éléments suivants k' < k dont il existe 2k-2 .

De tout cela, nous pouvons conclure :

• Si n ≥ 2ki and n < 2k(i+1) entonces i a :

  • 2ki-2 des descendants à un niveau inférieur à k

  • n - 2ki+1 descendants au niveau k ;

  • Total : n-1 des descendants.

• Si n ≥ 2k(i+1) and n < 2k+1i entonces i a :

  • exactement 2k+1-1 des descendants.

Grosso modo, cela signifie que le dernier 2k ne sont pas trouvés dans le premier 1/2k une partie du tableau sous-jacent du tas.