Comment supprimer dans une structure de données tas?
je comprends comment supprimer le noeud racine d'un tas max mais est la procédure pour supprimer un noeud du milieu pour enlever et remplacer la racine à plusieurs reprises jusqu'à ce que le noeud désiré est supprimé?
O (log n) est-il la complexité optimale de cette procédure?
est-ce que cela affecte la grande complexité O puisque d'autres noeuds doivent être supprimés pour supprimer un noeud spécifique?
4 réponses
en fait, vous pouvez retirer un article du milieu d'un tas 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. S'il n'est pas plus grand que le parent, alors tamisez-le vers le bas.
C'est la procédure pour un max heap. Pendant une minute, bien sûr, vous inverserez le plus grand et le moins cas.
Trouver un article dans un tas est une opération O(n), mais si vous savez déjà où il se trouve dans le tas, l'enlever Est O(log n).
j'ai publié une liste de priorités basée sur le tas pour DevSource il y a quelques années. Voir a Priority file Implementation in C#. Il a un RemoveAt méthode qui fait exactement ce que j'ai décrit.
la source complète est à http://www.mischel.com/pubs/priqueue.zip
mise à Jour
plusieurs ont demandé s'il est possible de bouger vers le haut après avoir déplacé le dernier noeud dans le tas pour remplacer le noeud supprimé. Considérez ce tas:
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 pour le déplacer jusqu'à le rendre valide tas:
1
3 2
6 8
la clé ici est que si l'article que vous remplacez est dans un autre subtree que le dernier élément dans le tas, il est possible que le noeud de remplacement sera plus petit que le parent du noeud remplacé.
le problème avec la suppression d'un élément arbitraire d'un tas est que vous ne pouvez pas le trouver.
dans un tas, chercher un élément arbitraire est O(n), donc supprimer un élément [s'il est donné par la valeur] est O(n).
S'il est important pour vous de supprimer les éléments arbitraires de la structure des données, un tas n'est probablement pas le meilleur choix, vous devriez considérer les structures de données triées complètes à la place comme balanced BST et passez liste.
Si votre élément est donné par référence, il est toutefois possible de le supprimer O(logn) en le "remplaçant" simplement par la dernière feuille [rappelez-vous qu'un tas est implémenté comme un arbre binaire complet, donc il y a une dernière feuille, et vous savez exactement où il est], supprimez ces éléments, et ré-heapifiez le sous tas pertinent.
si vous avez un tas max, vous pouvez implémenter ceci en assignant une valeur plus grande que n'importe quelle 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 effectuer une suppression régulière du noeud racine.
cela provoquera une nouvelle heapify, mais je ne vois pas de moyen évident d'éviter de le faire deux fois. Cela suggère que peut-être un tas n'est pas approprié pour votre cas d'utilisation, si vous besoin de tirer des noeuds du milieu de lui souvent.
(pour un min d'un segment, vous pouvez évidemment utiliser int.MinValue ou -inf ou autre)
ce que vous voulez réaliser n'est pas une opération de tas typique et il me semble qu'une fois que vous introduisez "delete middle element" comme méthode un autre arbre binaire(par exemple red-black ou AVL tree) est un meilleur choix. Vous avez un arbre rouge-noir implémenté dans certaines langues(par exemple map et set en c++).
sinon la façon de faire la suppression de l'élément central est celle proposée dans la réponse de rejj: Assignez une grande valeur (pour max heap) ou une petite valeur (pour min heap) à l'élément, passez-le au crible. jusqu'à la racine, puis le supprimer.
cette approche maintient toujours la complexité O(log(n)) Pour la suppression de l'élément central, mais celle que vous proposez le fait. Il aura comlexity O (N * log (n)) et par conséquent n'est pas très bon. Espérons que cela aide.