Comment supprimer un tas de structure de données?

Je comprends comment faire pour supprimer le nœud racine à partir d'un tas max, mais est la procédure de suppression d'un nœud à partir du milieu de retirer et remplacer la racine à plusieurs reprises jusqu'à ce que le nœud est supprimé?

  1. Est O(log n) la complexité optimale pour cette procédure?

  2. Cela affecte le big O complexité car les autres nœuds doivent être supprimés afin de supprimer un nœud spécifique?

  • pourquoi voulez-vous supprimer un nœud au milieu d'un tas max?
  • Une très réelle utilité d'une telle chose est un tas de représentation d'une file d'attente de priorité des tâches planifiées, et que quelqu'un annule l'un des emplois.
  • J'ai récemment mis en œuvre l'APL* algorithme de pathfinding, un remodelage de l'algorithme basé sur Un*. Il exige la capacité de se retirer du milieu de la priorité de la file d'attente.
  • En général, vous voulez poser une nouvelle question, plutôt que d'ajouter de nouvelles questions à l'un de quatre ans, l'ancien poste. Mais pour répondre à tes questions: 1) Dans un norme tas binaire, O(log n) est la meilleure complexité. 2) Suppression, à partir du milieu du tas ne sera jamais plus cher que la suppression du nœud racine, et que l'opération est déjà prouvé à O(log n). O(log n) est le pire des cas, la complexité de la suppression d'un nœud n'importe où dans le tas. Notez, cependant, que ce que j'ai indiqué dans ma réponse originale à cette question reste toujours vrai: il prend O(n) pour trouver le nœud à supprimer.
  • mathcs.emory.edu/~cheung/Cours/171/Programme/9-BinTree/...
InformationsquelleAutor tesfa koli | 2012-01-02
  1. 81

    En fait, vous pouvez supprimer un élément à partir du milieu d'un segment sans problème.

    L'idée est de prendre le dernier élément dans le tas et, à partir de la position actuelle (c'est à dire la position qui a tenu l'élément que vous avez supprimé), tamiser, si le nouvel élément est plus grand que le parent de l'ancien article. Si ce n'est pas plus grand que le parent, puis tamiser vers le bas.

    Que la procédure à suivre pour avoir un max de tas. Pour un min tas, bien sûr, vous souhaitez inverser les plus et les moins des cas.

    Trouver un élément dans un tas est un O(n) opérations, mais si vous savez déjà où il est dans le tas, la suppression il est O(log n).

    J'ai publié un heap file d'attente de priorité pour DevSource quelques années en arrière. Voir Une File d'attente de Priorité de mise en Œuvre en C#. Il a un RemoveAt méthode qui fait exactement ce que j'ai décrit.

    Source complet est à http://www.mischel.com/pubs/priqueue.zip

    Mise à jour

    Plusieurs ont demandé si il est possible de se déplacer jusqu'après le passage du dernier nœud dans le tas pour remplacer l'élément supprimé. Considérer ce segment:

            1
    6       2
  7   8   3

    Si vous supprimez le nœud avec la valeur 7, la valeur 3 remplace:

            1
    6       2
  3   8

    Vous avez maintenant de le déplacer jusqu'à le rendre valide tas:

            1
    3       2
  6   8

    La clé ici est que si l'article que vous êtes en remplaçant est dans un autre sous-arbre que le dernier élément dans le tas, il est possible que le nœud de remplacement sera plus petit que le parent de l'remplacé nœud.

    • Je ne suis pas tout à fait sûr que je vous comprends. Êtes-vous en train de dire que nous supprimer l'arbitraire et de remplacer sa position avec le dernier élément de la pile de l'arbre, et soit tamiser le haut ou vers le bas? Je doute que ce que vous dites parce que 1) Il ne peut tamiser jamais 2) L'arbre peut être pas complet du tout... Pouvez-vous développer? Je vous remercie.
    • C'est exactement ce que je dis. Et il ne fonctionne en effet. Jetez un oeil à mon exemple de code, ou de regarder n'importe quel segment de la mise en œuvre qui permet l'élimination.
    • Il peut effectivement tamiser car il pourrait ne pas être partie de la même arborescence. L'image de la racine au début de l'arbre est divisé en deux parties indépendantes. Vous pourriez être la suppression d'un nœud du sous-arbre gauche, mais si vous prenez le dernier élément de la dernier niveau du segment qui pourrait être un élément de la sous-arbre droit. Il n'y a pas de commande entre les sous-arbres, seulement par rapport à leur parent.
    • est de déplacer vers le haut possible pour une valeur pour le dernier élément d'un swap? également indices sont pour la plupart de moins en moins utilisées pour les segments qu'ils changent fréquemment, tout en poussant et en poping. quelle serait la stratégie pour supprimer en valeur?
    • Si vous souhaitez supprimer en valeur, vous devez maintenir un dictionnaire ou de hachage carte, clé en valeur, qui contient l'index de l'élément dans le tas. Et, oui, il est possible pour une valeur de déplacer vers le haut après la permutation. Voir ma mise à jour.
    • merci beaucoup pour l'explication
    • Votre lien est expiré.
    • Oui, le DevSource l'article a disparu. Le code de lien est toujours bon, mais.

    InformationsquelleAutor Jim Mischel
  2. 15

    Le problème avec la suppression de l'arbitraire d'un élément à partir d'un tas, c'est que vous ne pouvez pas le trouver.

    Dans un tas, à la recherche de l'arbitraire d'un élément est O(n), donc suppression d'un élément [si elle est donnée par la valeur] est O(n) ainsi.

    Si il est important pour vous de supprimer l'arbitraire des éléments de la forme de la structure des données, un segment de mémoire est probablement pas le meilleur choix, vous devriez envisager plein de trier les données structurs plutôt comme équilibré BST ou un ignorer la liste.

    Si votre élément est donné par référence, il est toutefois possible de le supprimer dans O(logn) simplement 'remplacer' avec la dernière feuille [souviens d'un tas est implémenté sous la forme d'un arbre binaire complet, donc il y a une dernière feuille, et vous savez exactement où il est], la suppression de ces élément, et re-heapify le sous segment.

    • Notez que vous pouvez trouver si vous êtes prêt à rouler votre propre tas de mise en œuvre. Vous avez juste besoin d'enregistrer une cartographie de l'objet à l'index, ou de dommage stocker l'index sur l'objet, et de le mettre à jour à chaque fois qu'il swaps éléments. Mise à jour n'est pas cher car il n'est jamais sur un swap, qui permet de permuter les indices; vous n'avez pas à faire toute la numérisation.
    InformationsquelleAutor amit
  3. 2

    Si vous avez un tas max, vous pouvez le mettre en attribuant une valeur plus grande que tout autre (par exemple quelque chose comme int.MaxValue ou inf dans la langue que vous utilisez) possible à l'élément à supprimer, puis re-heapify et il sera la nouvelle racine. Puis procéder à une élimination régulière du nœud racine.

    Ce sera la cause d'un autre re-heapify, mais je ne vois pas d'une manière évidente d'éviter de le faire deux fois. Ceci suggère que peut-être un tas n'est pas appropriée à votre cas d'utilisation, si vous avez besoin de pull nœuds à partir du milieu d'elle souvent.

    (pour un min d'un segment, vous pouvez évidemment utiliser int.MinValue ou -inf ou quoi que ce soit)

    InformationsquelleAutor rejj
  4. 1

    Ce que vous voulez atteindre est pas typique d'un tas de fonctionnement et il me semble que une fois que vous introduisez "supprimer le milieu de l'élément" comme une méthode de quelques autres arbres binaires(par exemple, rouge-noir ou arbre AVL) est un meilleur choix. Vous avez un rouge-noir arbre mis en œuvre dans certaines langues(par exemple la carte et définir en c++).

    Autrement la façon de le faire moyen de l'élément de suppression est proposée dans rejj réponse: attribuer une grande valeur(pour max tas) ou de faible valeur(par min tas) de l'élément, tamiser il jusqu'à la racine, puis le supprimer.

    Cette approche conserve encore l'O(log(n)) de la complexité pour le centre de l'élément de suppression, mais l'on vous propose n'. Il aura comlexity O(n*log(n)) et cet effet n'est pas très bonne.
    Espérons que cela aide.

    InformationsquelleAutor Ivaylo Strandjev