Comment déterminer la séquence de tas

On connaît une séquence, telle que {100,6070,50,32,65}, comment déterminer si c'est un tas ?

Réponse : Traitez cette séquence comme un arbre binaire de type tableau. Si le nœud racine est i, le sous-arbre de gauche est 2*i et le sous-arbre de droite est 2*i+1.

Le tas est divisé en un tas maximum et un tas minimum.

1. Tous les nœuds parents du tas maximum sont plus grands que le sous-arbre gauche et le sous-arbre droit. Par exemple, si une séquence connue est dessinée sous forme de tas :

La séquence connue est donc un tas maximum.

2. Tous les nœuds parents du tas minimum sont plus petits que le sous-arbre gauche et le sous-arbre droit, tels que {32,50,60,70,100,65}, dessinés comme un tas :

La séquence qui répond aux deux situations ci-dessus est un tas

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!