J'étudie pour quelques interviews techniques à venir et je ne faisais que passer en revue des diapositives de cours d'il ya un an ou deux sur les structures de données. Je ne comprends pas pourquoi les runtimes les plus défavorables de fusion pour un segment de gauche sont O (log n) alors que pour un segment de décalage, c'est O (n), quand un tas asymétrique fusionne essentiellement de la même manière que un tas de gauchiste.Les pires cas de Skew Heap vs Leftist Heap
Un tas de gauche fusionne A et B en sélectionnant l'arbre avec la racine la plus petite et en fusionnant récursivement son sous-arbre de droite avec l'arbre plus grand. Ensuite, il vérifie les longueurs de chemin nul et échange ses deux sous-arbres s'il enfreint la propriété de structure de gauche.
Un tas skew fait la même chose, mais permute aveuglément ses deux sous-arbres à chaque fois qu'il se confond récursive A et B.
Pourquoi le pire des cas de fusion pour un tas d'inclinaison devient O (n)? Est-ce parce que nous ne pouvons pas garantir une hauteur liée à la fusion récursive (puisqu'elle change de côté à chaque fois)? Est-ce que cela a à voir avec l'algorithme de Floyd, que la somme des hauteurs de tous les nœuds d'un arbre croît en O (n)?
Je ne me souviens pas vraiment de ces structures assez bien pour répondre, mais je peux vous dire que j'ai eu quelques entretiens techniques et d'après ce que j'ai vu, je serais surpris que cela se présente. La nature détaillée de votre question montre à elle seule une très bonne compréhension, et le temps que vous consacrerez à ces entretiens serait probablement mieux dépensé ailleurs. Cela dépend de la nature de votre travail bien sûr, mais d'après ce que j'ai vu, l'accent sur les discussions/processus/concurrence est probable. –