Comment faire pour supprimer à partir d'un Max-Heap?

Si nous avons mis 15 dans la racine, quel serait le processus de heapify?

            85
            /\
           / \
          /   \
        55      70
        /\      /\
       / \    / \
      22  33  30  65
     /\   /
   14 15 15

Ce que devrait être la façon de le supprimer de 85 dans le Tas?

  • tech-faq.com/deleting-an-element-from-a-heap.html
  • Pourquoi pas? 15 est inférieur à 33, de sorte que le segment de mémoire-propriété est satisfaite.
  • OK. Ma question n'était pas à ce point. J'ai modifié le tas. Juste essayer de supprimer 85 et dites-moi ce qui se passe.
  • Hm, vous avez raison. J'ai ajouté de l'arbre binaire de la propriété ainsi.
  • Le tas est ok. Le tas propery est que chaque parent est plus grande que son fils. Ce n'est pas un arbre binaire.
  • Je me demande qui upvoted "que l'arbre n'est pas un tas de"

InformationsquelleAutor user366312 | 2011-07-10
  1. 4

    Que vous êtes toujours en échangeant avec la plus grande des deux (le segment de la propriété signifie que le parent est toujours plus grand que ses enfants):

                15
            /\
           / \
          /   \
        55      70
        /\      /\
       / \    / \
      22  33  30  65
     /\   
   14 15

            70
            /\
           / \
          /   \
        55      15
        /\      /\
       / \    / \
      22  33  30  65
     /\   
   14 15

            70
            /\
           / \
          /   \
        55      65
        /\      /\
       / \    / \
      22  33  30  15
     /\   
   14 15
    InformationsquelleAutor Femaref
  2. 1

    Si vous supprimez 85 et de le remplacer avec de 15, vous tournez le demi-segment de retour dans un segment de mémoire par downheaping, c'est à dire le 15 à la racine de "puits" sur le chemin de grands enfants. Dans ce cas, il va échanger avec 70, puis à 65 ans.

    Edit: parce que nous sommes toujours permuter avec le plus grand enfant, il nous permet de retrouver avec un valide tas (par exemple, si nous avons échangé nos 15 à 55 au lieu de 70, on aurait 70 comme un enfant de 55 ans qui n'est pas bon)

    InformationsquelleAutor
  3. 0

    Pour ajouter vous mettez la nouvelle valeur en dernier (droit à 20 dans votre exemple), et puis vous essayez de résoudre le tas, c'est-à comparer avec ses parents, si elle est plus grande que le swap et les comparer à nouveau jusqu'à ce qu'aucun swap n'est pas nécessaire (ou vous obtenir à la racine)

    Afin de supprimer vous vous retirer de remplacer le dernier objet (15 en vous exemple) et de fixer le tas à la baisse.

    • Quand j'ai mis 15 à la racine et heapify, 55 devraient aller à la racine. Mais alors quoi? 70 est toujours candidat pour l'obtention de la racine. Alors devrions-nous heapify le sous-arbre droit aussi?
    • Non, la plus grande des deux obtient échangé. De sorte que le 70 sera la nouvelle racine.
    • N ° 55 ans ne devraient pas aller parce que cela signifie que le parent n'est pas plus grand que son fils qui est la propriété du tas.
    InformationsquelleAutor roni