Quand voudrais-je utiliser un tas?

89

Outre la réponse évidente d'une file d'attente prioritaire, quand un tas serait-il utile dans mes aventures de programmation?

Mithrax
la source
8
Il y a beaucoup de bonnes réponses ici, alors je vais ajouter "quand une pile n'est tout simplement pas assez grande".
Don Werve le

Réponses:

119

Utilisez-le chaque fois que vous avez besoin d'un accès rapide à l'élément le plus grand (ou le plus petit), car cet élément sera toujours le premier élément du tableau ou à la racine de l'arborescence.

Cependant, le reste du tableau est conservé partiellement non trié. Ainsi, l'accès instantané n'est possible qu'au plus gros (plus petit) élément. Les insertions sont rapides, c'est donc un bon moyen de gérer les événements ou les données entrants et d'avoir toujours accès aux plus anciens / plus importants.

Utile pour les files d'attente prioritaires, les planificateurs (où l'élément le plus ancien est souhaité), etc ...

Un tas est un arbre dans lequel la valeur d'un nœud parent est supérieure à celle de l'un de ses nœuds descendants.

Si vous pensez à un tas comme un arbre binaire stocké dans l'ordre linéaire par profondeur, avec le nœud racine en premier (puis les enfants de ce nœud ensuite, puis les enfants de ces nœuds ensuite); alors les enfants d'un nœud à l'indice N sont à 2N + 1 et 2N + 2. Cette propriété permet un accès rapide par index. Et comme les tas sont manipulés en échangeant des nœuds, cela permet un tri sur place.

Joe Koberg
la source
3
Notez également qu'il peut être une sorte NlogN garantie pratique qui ne nécessite pas de tableau des allocations supplémentaires
survolée
37
C'est aussi génial de connaître des tas de questions d'entrevue;)
vivekian2
19
@ vivekian2 La seule raison pour laquelle je suis ici est que je suis sur le point d'avoir une interview.
byxor
pourquoi ne pas utiliser une classe de pile avec une pile auxiliaire pour suivre le plus grand (ou le plus petit) élément. la récupération est O (1)
Ridhwaan Shakeel
@RidhwaanShakeel Si vous utilisez la pile, votre objet sera toujours placé sur la tête, que se passe-t-il si la position de l'objet doit être déterminée en fonction d'une propriété de l'objet comme le plus grand événement (basé sur le nombre de personnes ayant participé à l'événement).
SandeepGodara
48

Les tas sont des structures destinées à permettre un accès rapide au min ou au max .

Mais pourquoi voudriez-vous cela? Vous pouvez simplement vérifier chaque entrée sur ajouter pour voir si c'est la plus petite ou la plus grande. De cette façon, vous avez toujours le plus petit ou le plus grand en temps constant O(1).

La réponse est que les tas vous permettent de tirer le plus petit ou le plus grand et de connaître rapidement le SUIVANT le plus petit ou le plus grand . C'est pourquoi cela s'appelle une file d'attente prioritaire.

Exemple du monde réel (pas très juste, cependant):

Supposons que vous ayez un hôpital dans lequel les patients sont soignés en fonction de leur âge. Les plus âgés sont toujours suivis en premier, peu importe quand ils sont dans la file d'attente.

Vous ne pouvez pas simplement garder une trace du plus vieux parce que si vous le retirez, vous ne connaissez pas le plus ancien suivant. Afin de résoudre ce problème d'hôpital, vous implémentez un tas maximum . Ce tas est, par définition, partiellement ordonné. Cela signifie que vous ne pouvez pas trier les patients en fonction de leur âge, mais vous savez que les plus âgés sont toujours en haut, vous pouvez donc retirer un patient en temps constant O(1)et rééquilibrer le tas en temps de journal O(log N).

Exemple plus sophistiqué:

Supposons que vous ayez une séquence d'entiers et que vous vouliez garder une trace de median . La médiane est le nombre qui se trouve au milieu d'un tableau ordonné.

Exemple:

[1, 2, 5, 7, 23, 27, 31]

Dans le cas ci-dessus, 7est la médiane car le tableau contenant les plus petits nombres [1, 2, 5]est de la même taille que celui contenant les plus grands nombres [23, 27, 31]. Normalement, si le tableau a un nombre impair d'éléments, la médiane est la moyenne arithmétique des 2 éléments au milieu, par exemple (5 + 7)/2.

Maintenant, comment faites-vous le suivi de la médiane? En ayant 2 tas , un tas min contenant les nombres inférieurs à la médiane actuelle et un tas max contenant les nombres plus grands que la médiane actuelle. Maintenant, si ces tas sont toujours équilibrés, les 2 tas contiendront le même nombre d'éléments ou l'un aura 1 élément de plus que l'autre, le plus.

Lorsque vous ajoutez un nouvel élément à la séquence, si le nombre est inférieur à la médiane actuelle, vous l'ajoutez au tas min, sinon, vous l'ajoutez au tas max. Maintenant, si les tas sont déséquilibrés (un tas a plus d'un élément de plus que l'autre), vous tirez un élément du plus grand tas et l' ajoutez au plus petit. Maintenant, ils sont équilibrés.

André Pena
la source
4
L'exemple le plus sophistiqué est incroyable! Je vais certainement essayer ça un jour. Cependant, je pense qu'il y a une petite erreur dans votre exemple. Puisque nous devons obtenir la médiane en faisant la moyenne des deux éléments au milieu. Je suppose que nous devons utiliser un tas min pour stocker les nombres plus grands que la médiane actuelle et un tas max pour stocker les nombres plus petits que la médiane actuelle. De cette façon, nous pouvons extraire les deux éléments du milieu en temps constant et calculer la médiane? Ai-je raison?
Calvin Ku
12

La caractéristique d'un tas est qu'il s'agit d'une structure qui maintient les données semi-ordonnées; c'est donc un bon compromis entre le coût de maintien d'un ordre complet et le coût de recherche dans le chaos aléatoire. Cette caractéristique est utilisée sur de nombreux algorithmes, tels que la sélection, le classement ou la classification.

Une autre caractéristique utile d'un tas est qu'il peut être créé sur place à partir d'un tableau!

AticusFinch
la source
3

Convient également aux algorithmes de sélection (trouver le min ou le max)

Dan
la source
3

à tout moment lorsque vous triez une liste temporaire, vous devriez envisager des tas.

Javier
la source
0

Vous pouvez utiliser un minHeap ou un maxHeap lorsque vous souhaitez accéder respectivement aux éléments les plus petits et les plus grands.

QuadBiker
la source