Qu'est-ce qu'une liste de priorités ?
Une liste de sauts est une structure de données probabiliste. La liste de sauts est utilisée pour stocker une liste triée d'éléments ou de données avec une liste chaînée. Il permet de visualiser efficacement le processus des éléments ou des données. En une seule étape, il saute plusieurs éléments de la liste entière, c'est pourquoi on l'appelle liste de saut.
La liste de sauts est une version étendue de la liste chaînée. Il permet à l'utilisateur de rechercher, supprimer et insérer l'élément très rapidement. Il se compose d'une liste de base qui comprend un ensemble d'éléments qui maintient la hiérarchie des liens des éléments suivants.
Structure de la liste de sauts
Il est construit en deux couches : la couche la plus basse et la couche supérieure.
La couche la plus basse de la liste à sauter est une liste chaînée triée commune, et les couches supérieures de la liste à sauter sont comme une « ligne express » où les éléments sont ignorés.
Tableau de complexité de la liste à sauter
| Oui Non | Complexité | Cas moyen | Pire cas |
|---|---|---|---|
| 1. | Complexité d’accès | O (connexion) | Sur) |
| 2. | Complexité de la recherche | O (connexion) | Sur) |
| 3. | Supprimer la complexité | O (connexion) | Sur) |
| 4. | Insérer de la complexité | O (connexion) | Sur) |
| 5. | Complexité spatiale | - | O (nlogn) |
Fonctionnement de la liste de sauts
Prenons un exemple pour comprendre le fonctionnement de la liste de sauts. Dans cet exemple, nous avons 14 nœuds, de sorte que ces nœuds sont divisés en deux couches, comme le montre le diagramme.
La couche inférieure est une ligne commune qui relie tous les nœuds, et la couche supérieure est une ligne express qui relie uniquement les nœuds principaux, comme vous pouvez le voir sur le diagramme.
Supposons que vous souhaitiez trouver 47 dans cet exemple. Vous commencerez la recherche à partir du premier nœud de la ligne express et continuerez à courir sur la ligne express jusqu'à ce que vous trouviez un nœud égal à 47 ou supérieur à 47.
Vous pouvez voir dans l'exemple que 47 n'existe pas dans la ligne express, vous recherchez donc un nœud inférieur à 47, soit 40. Maintenant, vous allez sur la ligne normale à l'aide de 40, et recherchez le 47, comme le montre le schéma.
Remarque : Une fois que vous avez trouvé un nœud comme celui-ci sur la « ligne express », vous passez de ce nœud à une « voie normale » à l'aide d'un pointeur, et lorsque vous recherchez le nœud dans la ligne normale.
Ignorer les opérations de base de la liste
Il existe les types d’opérations suivants dans la liste de sauts.
Algorithme de l'opération d'insertion
Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a
Algorithme d'opération de suppression
Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1
Algorithme d'opération de recherche
Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure
Exemple 1: Créez une liste de sauts, nous voulons insérer ces clés suivantes dans la liste de sauts vide.
- 6 avec niveau 1.
- 29 avec niveau 1.
- 22 avec niveau 4.
- 9 avec niveau 3.
- 17 avec niveau 1.
- 4 avec niveau 2.
Ans:
Étape 1: Insérer 6 avec niveau 1
Étape 2: Insérer 29 avec niveau 1
Étape 3: Insérer 22 avec niveau 4
Étape 4: Insérer 9 avec niveau 3
Étape 5 : Insérer 17 avec niveau 1
Étape 6 : Insérer 4 avec niveau 2
Exemple 2 : Prenons cet exemple où nous voulons rechercher la clé 17.
Ans:
Avantages de la liste de sauts
- Si vous souhaitez insérer un nouveau nœud dans la liste de sauts, il insérera le nœud très rapidement car il n'y a pas de rotations dans la liste de sauts.
- La liste de sauts est simple à mettre en œuvre par rapport à la table de hachage et à l'arbre de recherche binaire.
- Il est très simple de trouver un nœud dans la liste car il stocke les nœuds sous forme triée.
- L'algorithme de liste de sauts peut être modifié très facilement dans une structure plus spécifique, telle que des listes de sauts indexables, des arbres ou des files d'attente prioritaires.
- La liste de sauts est une liste robuste et fiable.
Inconvénients de la liste de sauts
- Il nécessite plus de mémoire que l’arbre équilibré.
- La recherche inversée n'est pas autorisée.
- La liste de saut recherche le nœud beaucoup plus lentement que la liste chaînée.
Applications de la liste de saut
- Il est utilisé dans les applications distribuées et représente les pointeurs et le système dans les applications distribuées.
- Il est utilisé pour implémenter une file d'attente simultanée élastique dynamique avec un faible conflit de verrouillage.
- Il est également utilisé avec la classe de modèle QMap.
- L'indexation de la liste de sauts est utilisée dans l'exécution de problèmes médians.
- La liste de sauts est utilisée pour la publication avec codage delta dans la recherche Lucene.