Algorithme pour garder la collection triée en insérant au milieu

Question

Disons que j'ai une grande collection d'éléments.
Chaque élément a un champ "position", qui est un nombre entier positif.
Aucun élément n'a la même valeur pour le champ "position".

La seule a soutenu l'opération de la collection est: addElement (newElement, positionAfterElement), où:
- newElement est le nouvel élément à ajouter (sa position est inconnue pour l'instant)
- positionAfterElement est un élément existant de la collection.

La fonction garantit que:
- Position (positionAfterElement) Position < (newElement)
- aucun autre élément de la collection a une position entre la position (positionAfterElement) et la position (newElement)

je peux changez la valeur de toutes les positions d'élément comme je souhaite mais je veux réduire au minimum le nombre de changements (en moyenne).

Comment dois-je implémenter la fonction addElement?

Je pourrais juste pousser tous les éléments avec des positions plus élevées de 1, mais je suis sûr qu'il doit y avoir une meilleure façon de le faire.

Merci à tous pour votre aide.

Answer 1

OK, voici donc ce que je mis en œuvre, en pseudo-code:

addElement(newElement, positionAfterElement): 
    p0 <- positionOf(positionAfterElement) 
    c <- 5 
    finished <- false 
    while (not finished): 
     search for all elements which positions are in the range [p0 + 1, p0 + c] 
     if there are less than c elements in that range: // the range is not full 
      adjust position of elements in the range, and position of newElement, 
      so that 
       - elements are correctly ordered 
       - element positions are "evenly spread out" within the range 
      finished <- true 
     else:            // the range is full 
      c <- c * 2 
    end while 
end addElement 

Answer 2

Voici une idée de base:

expected_number_of_elements = 10^6 
spread_factor = 100 
first element gets position = spread_factor * expected_number_of_element 
each following element inserted: 
    if its inserted in last position, give it the last element's position + spread_factor 
    if its inserted in the first position, give it the first element's position - spread_factor 
    otherwise, put it in the middle between its 2 closest neighbors 
    if you don't have any space left: expand_the_array 


expand_the_array: 
    spread_factor = spread_factor * 10 
    iterate over all the elements, and multiply position by 10. 

extension du module RAID est une opération coûteuse, mais puisqu'il multiplie la taille du tableau, en moyenne (en supposant que votre entrée est aléatoire, et non conçu par un adversaire) vous devrez faire cette opération très rarement.

l'inconvénient majeur de cette solution est que vous aurez à surveiller le débordement int ....

Answer 3

Utilisez un arbre équilibré. À chaque nœud de l'arbre, comptez le nombre d'éléments en dessous (left.count + right.count + 1). Ensuite, vous pouvez facilement calculer l'index d'un objet en le parcourant. C'est O (n log n) temps dans le nombre d'opérations.