Ces deux semblent très similaires et ont une structure presque identique. Quelle est la différence? Quelles sont les complexités temporelles pour les différentes opérations de
Combien de tas max différents existent pour une liste de nnn entiers? Exemple: liste [1, 2, 3, 4] Le tas max peut être soit 4 3 2 1: 4 / \ 3 2 / 1 ou 4 2 3 1: 4 / \ 2 3 / 1
Dans de nombreuses discussions sur le tas binaire, seule la touche de diminution est normalement répertoriée comme opération prise en charge pour un tas min. Par exemple, CLR chapitre 6.1 et cette page wikipedia . Pourquoi la clé d'augmentation n'est-elle pas normalement répertoriée pour le segment...
Très probablement, cette question est posée avant. C'est du problème 6.5-8 de CLRS (2nd Ed) - Donnez un algorithme de temps pour fusionner listes triées en une seule liste triée, où est le nombre total d'éléments dans toutes les listes d'entrée. (Astuce: utilisez un min-tas pour la fusion -way.)k n...
J'ai besoin d'aide pour comprendre la fonction potentielle d'un tas max afin que l'extraction max soit terminée en temps amorti. Je dois ajouter que je n'ai pas une bonne compréhension de la méthode potentielle.O ( 1 )O(1)O(1) Je sais que la fonction d'insertion devrait "payer" davantage afin de...
Les tas soudables randomisés ont une opération "fusion", que nous utilisons ensuite pour définir toutes les autres opérations, y compris l'insertion. La question est, quelle est la hauteur attendue de cet arbre à nnn nœuds? Le théorème 1 de Gambin et Malinkowski, Randomized Meldable Priority Queues...