Tas binaire et file d'attente prioritaire minimum orienté

Question

quelqu'un pourrait-il me dire lequel de ces tas binaires (max) et lesquels sont des files d'attente prioritaires minimum orientées, et pourquoi/pourquoi pas? Je les posterai dans des tableaux car je ne sais pas comment publier des images ici, les x signifient que cette position est vide.

On y va: [8,6,7,4,6,6, x], [4,5,4,7,8,4,6], [, 4,4,5,7, x, x, 6]

Je suppose que le premier est un tas binaire, et les deux autres sont la file d'attente prioritaire minimum orientée, mais selon les solutions que je me trompe. Les solutions peuvent cependant être fausses, donc s'il vous plaît, si vous savez lequel est, veuillez m'expliquer.

Merci d'avance.

Answer 1

Eh bien, le premier pourrait être un tas binaire max. Autrement dit, l'arbre ressemblerait à ceci:

  8 
     6  7 
    4 6 6 

Le second est un tas binaire min:

  4 
     5  4 
    7 8 4 6 

Le troisième ne peut pas être un tas binaire, car il ne se conforme pas à la forme la propriété. C'est-à-dire, cela correspondrait à:

  4 
    4  5 
    7 x x 6 

Dans un tas binaire, la rangée du bas est remplie à gauche. Cet arbre n'est pas rempli à gauche. Par conséquent, le premier est un tas binaire maximum. La seconde est un tas binaire min, qui peut également être vu comme une file d'attente prioritaire min-orientée. Je ne sais pas comment appeler le troisième. Ce n'est pas un min tas valide, et ce n'est pas une représentation séquentielle d'une file d'attente de priorité minimale, parce que 7 vient avant 6.

Au moins, c'est ma réponse basée sur ma compréhension des tas binaires et les files d'attente prioritaires.