Bonjour à tous

Dans le cadre d'un projet, je dois implémenter la structure d'arbre particulière appelée Min-Max Heap, càd un arbre dont la racine contient l'élément de valeur minimum et les fils de la racine contiennent les éléments de valeur maximum.

L'arbre obéit aussi à d'autres règles :
Les niveaux de l'arbre sont soit de type Min, soit de type Max (Un niveau sur 2 est de type min (comme le niveau de la racine), et vice-versa).

Ainsi, un niveau Max de l'arbre contient des noeuds dont la valeur est plus grande ou égale à celles de son père et de ses fils.
Inversement, un niveau Min de l'arbre contient des noeuds dont la valeur est inférieure ou égale à celles du père et des fils.


J'ai implémenté les fonctions de création, d'insertion, de suppression du minimum et de suppression du maximum.

Mais j'ai du mal à trouver comment implémenter la recherche du Kième élément le plus petit de l'arbre.

En effet, l'arbre n'est pas ordonné puisqu'un niveau sur 2 est de type Min, et un niveau sur 2 est de type Max, et aussi car le fils droit d'un noeud peut tout aussi bien être plus grand, plus petit ou égal au fils gauche...

Bref, je cherche des pistes m'indiquant comment implémenter de façon optimale cette fonction de recherche dans un Min-max Heap. Je me suis intéressé à une structure appelée order-statistics tree et qui semble en permettre une implémentation efficace, mais je ne trouve que peu de documentation à ce sujet, qui me permettrait de savoir comment améliorer ma structure actuelle.

Quelqu'un aurait-il des informations pouvant m'aider ?
Merci