En ce qui concerne l'espace, il y a très peu de problème avec l'utilisation des tableaux si vous savez à l'avance combien ils vont dans le tas - vos valeurs dans le tas peuvent toujours être des pointeurs vers des structures plus grandes. Cela peut permettre une meilleure localisation du cache sur le tas lui-même, mais il vous faudra encore sortir quelque part en mémoire pour des données supplémentaires. Idéalement, si votre comparaison est basée sur un petit morceau de données (souvent juste un float ou un entier de 4 octets), vous pouvez stocker cela comme clé avec un pointeur vers les données complètes et obtenir une bonne cohérence de cache.
Les tris de segment ne sont déjà pas particulièrement bons sur les hits de cache tout au long de la traversée de la structure de segment elle-même. Pour les petits tas qui s'intègrent entièrement dans le cache L1/L2, ce n'est pas si grave. Cependant, comme vous commencez à frapper la performance de la mémoire principale va plonger la bombe. Habituellement ce n'est pas un problème, mais si c'est le cas, le tri par fusion est votre sauveur.
Le plus gros problème survient lorsque vous voulez un tas de taille indéterminée. Cependant, ce n'est pas si mal, même avec des tableaux. De plus, dans des environnements non-embarqués avec de jolis et jolis systèmes de mémoire développant un tableau avec quelques appels (par exemple, realloc, veuillez pardonner mon arrière-plan C) n'est vraiment pas très lent car les données n'ont pas besoin de se déplacer physiquement en mémoire. un peu de magie de pointeur d'adresse pour la plupart. Ajouté au fait que si vous utilisez une stratégie de doublage de taille de tableau (array est trop petit, doublez la taille dans un appel de realloc) vous vous retrouvez avec un coût amorti de O (n) avec relativement peu de reallocs et au plus double gaspillage d'espace - mais bon, vous obtiendriez cela avec des listes liées de toute façon si vous utilisez une clé 32 bits et un pointeur 32 bits. Donc, en bref, je m'en tiendrai aux tableaux pour les plus petites structures de données de base. Lorsque le tas disparaît, les pointeurs dont je n'ai plus besoin avec une seule désallocation le sont aussi. Cependant, à mon avis, il est plus facile de lire le code basé sur un pointeur pour les tas, car traiter la magie de l'indexation n'est pas aussi simple. Si la performance et la mémoire ne sont pas un souci, je le recommanderais à tout le monde en un clin d'œil.
Je pense qu'un tableau serait la seule implémentation que vous voudriez prendre en compte, en raison de l'accès basé sur l'index à temps constant. Les listes liées ne peuvent pas faire cela. –
Je sais que pour un tri en tas, vous avez besoin du tableau à cause de l'index, mais qu'en est-il de toute autre utilisation pour un tas, comme si vous l'utilisiez comme une file d'attente prioritaire. Dans ce cas, je pense que pour les valeurs élevées de n (n étant le nombre d'éléments), l'espace gaspillé dans les emplacements vides d'un tableau représente un gaspillage plus important que la mémoire occupée par les nœuds et les pointeurs du tas lié. – Topo
Je pense que je reçois la direction de votre question maintenant; il ne s'agit pas de "devrais-je utiliser des tableaux ou des listes chaînées pour implémenter le tri de tas", c'est "dans différentes situations, quand serait-il préférable d'utiliser une liste chaînée pour un tas plutôt qu'un tableau". La façon dont vous avez formulé votre question, il semble que vous posez seulement des questions sur les implémentations de tri de tas. –