tout usage de tas binaire

Définition:

Une file d'attente de priorité est un type de données abstrait, qui est comme une file d'attente régulière ou structure de données pile, mais où en outre chaque élément a une « priorité » qui lui est associée . Dans une file d'attente prioritaire, un élément de haute priorité est servi avant un élément de faible priorité. Si deux éléments ont la même priorité, ils sont servis selon leur ordre dans la file d'attente.tout usage de tas binaire

Mise en œuvre:

Pour mettre en œuvre file d'attente prioritaire, tableau non trié, tableau trié et tas binaire structure de données sont les 3 stratégies de mise en œuvre.

Pour être précis, tas binaire stratégie de mise en œuvre peut être représentée à l'aide tableau de clés,

ou

chaque clé comme noeud binaire ayant deux enfants .

Question:

En dehors de la mise en œuvre de la file d'attente prioritaire, sont leurs d'autres applications à l'aide de tas binaire structure de données?

Source

2017-01-04 overexchange

Voir aussi tri par tas. –

Pas vraiment. On pourrait même prétendre que l'on peut même dire qu'il suffit de peupler une file d'attente prioritaire, puis de retirer les choses dans l'ordre. Le tas binaire * est * une file d'attente prioritaire.La question la plus importante est de savoir quelles sont les applications des files d'attente prioritaires et, parmi celles-ci, qui sont mieux implémentées avec un tas binaire et qui devraient utiliser une autre implémentation de file d'attente prioritaire. –

1. Veuillez fournir l'attribution correcte pour la source d'où vous avez copié cela. Voir http://stackoverflow.com/help/referencing. 2. Demander une liste de toutes les applications de tas binaires est probablement trop large. 3. Quelles recherches avez-vous faites? Avez-vous regardé dans les manuels de structures de données pour voir ce qu'ils font avec un tas? –

Un tas binaire peut être utilisé pour extraire l'élément (max ou min) en temps O (logn). Cette propriété peut être exploitée pour être utilisée dans de nombreux algorithmes afin d'obtenir une meilleure exécution. Par exemple, une fois que je l'ai utilisé dans l'algorithme de tri k-merge pour augmenter l'efficacité temporelle de l'étape de tri du tri k-merge. En bref, il a fait des tas binaires des k-subarrays, et le tri peut être réalisé en temps linéaire, ce qui est meilleur que l'étape de tri habituelle d'un tri par fusion.

Il est également utilisé dans l'algorithme de Dijkstra, l'algorithme de Prim pour réduire leur temps d'exécution.

Vous pouvez également jeter un oeil here

Source

2017-01-04 09:58:27 CODError

Vous ne pouvez pas extraire des éléments d'un tas binaire à temps constant. * delete-min * est une opération O (log n). De plus, l'OP a demandé des utilisations de tas binaires autres que l'implémentation d'une file d'attente prioritaire. Vos trois exemples (tri par fusion, algorithme de Dijkstra, algorithme de Prim) sont basés sur des files d'attente prioritaires. Le tas binaire est juste une implémentation pratique. –

J'ai corrigé ma réponse. merci de l'avoir signalé. J'essaie d'énumérer le peu d'utilisation des tas binaires. Je n'ai pas parlé de la mise en œuvre. Si vous avez une situation où vous n'utilisez pas un tas binaire en tant que file d'attente prioritaire, vous pouvez laisser un commentaire. Je serai heureux d'apprendre. – CODError

"Extraire (max ou min) élément" - c'est pratiquement la définition d'une file d'attente prioritaire, donc vous n'avez pas répondu à la question, comme l'a souligné @JimMischel. \t "Si vous n'utilisez pas un tas binaire comme file d'attente prioritaire", vous l'avez en arrière. Il y a plusieurs façons d'implémenter des files d'attente de priorité sans utiliser de tas ... l'OP mentionne les tableaux triés et non triés, et il y en a beaucoup d'autres. La question est de savoir si les tas binaires sont bons pour autre chose. Voir ma réponse pour ... une réponse réelle. Edit: Je pense que peut-être tu n'as pas eu de recul, juste mal formulé. –

tas binaires ont une autre application utile (et importante): HeapSort. HeapSort a un surdébit supérieur à QuickSort mais son pire cas est O (n log n) par rapport à O (n * n) de QuickSort. QuickSort peut être amélioré pour obtenir le pire cas de O (n log n) en basculant vers HeapSort lorsque l'intervalle est suffisamment court - cela s'appelle IntroSort, et c'est ce qui est utilisé dans la bibliothèque STL et la bibliothèque standard C++. Voir https://en.wikipedia.org/wiki/Introsort

Source

2017-01-05 08:42:33

tout usage de tas binaire

Définition:

Mise en œuvre:

Répondre

Questions connexes