Qu'est-ce que l'utilisation des Tas de structure de données?

Je travaille sur certains devoirs impliquant des Tas, et je comprends comment ils sont structurés. Un tas doit avoir chaque nœud satisfaisant la propriété tas,

max-tas de propriété, c'est que pour
chaque noeud i les autres, puis la racine,
Tas[Parent(i)] >= Tas[i]

Donc à chaque nœud, les nœuds supérieurs ont un plus grand nombre, les nœuds inférieurs ont des numéros les plus bas. Je comprends cela. Mais je ne peux pas voir une utilisation d'un Tas d'autres ensuite simplement à obtenir le plus haut n nombres dans une liste. Je ne vois pas un moyen facile de rechercher une valeur particulière et retour le nœud, ou à la recherche de la n plus petit nombre (en un max-heap). Les deux sont relativement facile dans un arbre de recherche binaire.

Pourquoi ne pas simplement utiliser un simple arbre de recherche binaires? Ou mieux encore, un équilibre binaire un arbre de recherche?

EDIT:
Je tiens à souligner, que ce n'est pas la recherche d'une réponse à un problème. Le réel problème est l'écriture de pseudo-parallèle-p-tas pour l'insert() et extractMax (). Et j'ai déjà répondu. Ils ont juste fait je me rends compte que je ne comprends pas vraiment des Tas.

double possible de Quand je veux utiliser un segment de mémoire?
J'ai cherché la réponse sur la manière, mais raté. Et oui, on dirait que je suis une dup. Dois-je fermer ma question?
Pas de besoin. Il est sur le point d'être fermé par nous, mais de dup sont généralement considérés comme de Bonnes Choses, car il n'y a plus d'une façon de poser la même question.
fonctionne pour moi, j'ai eu ma réponse.
déplacer ce commentaire pour une réponse et je vais l'accepter.

OriginalL'auteur jb. | 2011-03-08

  1. 5

    En raison de l'absence de pointeurs (tas généralement utiliser un tableau basé sur les données de la structure), les exploitations ont tendance à être plus rapide que pour un arbre binaire. Aussi, d'autres plus compliqués tas (comme binomiale) peuvent être fusionnés de manière efficace, ce qui n'est pas facile à faire pour un arbre binaire. Il y a aussi de l'information disponible à cette SORTE de question.

    OriginalL'auteur Jeremiah Willcock

  2. 13

    Le tas structure de données a de nombreuses applications.

    • Heapsort: l'Un des meilleures méthodes de tri en place et sans quadratique dans les pires scénarios.
    • Algorithmes de sélection: Trouver le min, max, le min et le max, médiane, ou même la k-ième plus grand élément peut être fait en temps linéaire (souvent à temps constant) à l'aide de segments.[4]
    • Algorithmes sur les graphes: En utilisant des tas interne de la traversée des structures de données, le temps de parcours sera réduit par ordre polynomial. Des exemples de tels problèmes sont Prim minimal spanning tree et algorithme Dijkstra plus court chemin de problème.

    Complet et presque complète tas binaire peut être représenté dans un espace très-efficace à l'aide d'un tableau à lui seul. Le premier (ni le dernier) de l'élément contient la racine. Les deux éléments de la matrice de contenir ses enfants. Les quatre prochaines contenir les quatre enfants de deux nœuds enfants, etc. Ainsi, les enfants du nœud à la position n serait à des positions 2n et 2n+1 dans un tableau, ou 2n+1 et 2n+2 dans un tableau de base zéro. Cela permet de déplacer vers le haut ou vers le bas de l'arbre en faisant simple indice de calculs. L'équilibrage d'un segment de mémoire est fait par le remplacement des éléments qui sont hors de l'ordre. Comme nous pouvons construire un segment à partir d'un tableau sans nécessiter plus de mémoire (pour les noeuds, par exemple), heapsort peut être utilisé pour trier un tableau en place.

    Un avantage de plus de monceaux sur les arbres, dans certaines applications, est que la construction de tas peut être fait en temps linéaire à l'aide de l'algorithme de Tarjan.

    Référence: http://en.wikipedia.org/wiki/Heap_%28data_structure%29

    OriginalL'auteur Ashish