Comment puis-je trouver la médiane des nombres dans le temps linéaire en utilisant des tas?

Wikipedia dit:

Algorithmes de sélection: Trouver le min, max, le min et le max, la médiane ou même le k-ème élément le plus grand peut être fait en temps linéaire en utilisant des tas.

Tout ce qu’il dit, c’est que cela peut être fait, et non comment.

Pouvez-vous me donner un début sur la façon dont cela peut être fait en utilisant des tas?

    Vous utiliseriez un tas min-max-médian pour trouver le min, le max et la médiane en temps constant (et prendre un temps linéaire pour construire le tas). Vous pouvez utiliser des arbres de statistiques de commande pour trouver la valeur la plus petite / la plus petite. Ces deux structures de données sont décrites dans cet article sur les tas min-max [lien pdf] . Les tas min-max sont des tas binarys qui alternent entre min-heaps et max-heaps.

    A partir du papier: Un tas min-max-médian est un tas binary avec les propriétés suivantes:

    1) La médiane de tous les éléments est située à la racine

    2) Le sous-arbre gauche de la racine est un tas min-max Hl de taille plafond [((n-1) / 2)] contenant des éléments inférieurs ou égaux à la médiane. Le sous-arbre de droite est un tas max-min Hr de taille floor [((n-1) / 2)] contenant uniquement des éléments supérieurs ou égaux à la médiane.

    Le papier continue pour expliquer comment construire un tel tas.

    Edit: Après avoir lu l’article plus en détail, il semble que la construction des tas de médiane min-max nécessite que vous trouviez d’abord la médiane (FTA: “Trouver la médiane de tous les n éléments en utilisant l’un des algorithmes de temps linéaire connus”) . Cela dit, une fois que vous avez construit le tas, vous pouvez maintenir la médiane simplement en maintenant l’équilibre entre le tas min-max à gauche et le tas max-min à droite. DeleteMedian remplace la racine par le min du tas max-min ou le maximum du tas min-max (selon le maintien du solde).

    Donc, si vous prévoyez d’utiliser un tas min-max-median pour trouver la médiane d’un dataset fixe, vous êtes SOL, mais si vous l’utilisez sur un dataset changeant, c’est possible.

    Voir cette page Wikipédia sur les algorithmes de sélection . En particulier, regardez l’algorithme BFPRT et l’algorithme Median of Medians. BFPRT est linéairement probabiliste, et est modélisé sur quicksort; La médiane des médianes est garantie linéaire, mais présente un facteur constant important et peut donc prendre plus de temps dans la pratique, selon la taille de votre jeu de données.

    Si vous ne disposez que de quelques centaines ou de milliers d’éléments pour sélectionner la médiane, je suppose qu’un simple sorting rapide suivi d’une indexation directe est plus facile.

    Il existe probablement de meilleurs algorithmes, mais voici comment je le ferais:

    Avoir deux seaux et une valeur. La valeur est la médiane, les deux compartiments sont “plus grands que la médiane” et “plus petits que la médiane”. Pour chaque élément x du tableau, rééquilibrez les big_bucket telle sorte que big_bucket et small_bucket diffèrent pas plus de 1 par leur taille. Lorsque vous déplacez des objects du grand seau au petit seau, ils doivent d’abord passer par la valeur médiane pour y arriver (en d’autres termes, une différence de 2 poussera un élément d’un seau à l’autre – une différence de 1 poussera un élément). d’une valeur à la valeur médiane.) À la fin du premier passage dans le tableau, la valeur doit être la médiane.

    Peut-être que ce n’était pas là quand la question initiale a été posée, mais maintenant, wiki a un lien vers la source, et la voici: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027. pdf

    spécifiquement, allez à la page 17, et regardez la description de RSEL4. Ils prouvent dans le théorème 3.2 que la complexité temporelle de ce k-ième algorithme de sélection est O (k). il vous faudrait donc O (n) pour créer le tas, et un O (k) supplémentaire pour trouver le plus petit élément k.

    ce n’est pas vraiment aussi simple que certaines des autres réponses ont suggéré

    Si vous en savez plus sur la structure des données du tas, vous comprendrez facilement que c’est effectivement le cas. La structure du tas peut être construite en O (n), il y a min heap et max heap. L’élément racine min heap vous donnera le plus petit élément. l’élément racine max heap vous donnera l’élément max. Juste en construisant le tas, vous trouvez le min et le max. Même idée pour la médiane et la kième plus grande, en construisant votre tas, vous pouvez trouver la médiane et la kième plus grande en regardant la twig gauche ou droite de l’arbre et en gardant une quantité constante de mémoire pour stocker le numéro d’élément. etc.

    Stockez le premier nombre entier dans le tableau et définissez un compteur sur 1. Puis parcourez les entiers restants dans le vecteur. Si le nombre entier actuel dans le tableau est identique à celui stocké, le compteur est augmenté de un, sinon le compteur est diminué de un. Si le compteur atteint zéro, jetez l’entier stocké et remplacez-le par l’entier actuel du tableau. Lorsque vous avez finalement parcouru tous les nombres entiers, vous vous retrouvez avec un candidat. Vous devez ensuite parcourir à nouveau le tableau et compter l’occurrence du candidat pour vérifier qu’il s’agit bien d’un dominateur.

     static int FindDominator(int[] arr) { int counter = 1; int candidate = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] == candidate) counter++ else { counter--; if(counter == 0) { candidate = arr[i]; counter = 1; } } } counter = 0; for(int i = 0; i < n; i++) { if(arr[i] == candidate) counter++; } if(counter > n / 2) return candidate; else return -1; } 

    De toute évidence, min et max dans O (n) sont faciles et ne nécessitent pas de tas.

    Le plus grand peut être fait assez simplement en maintenant un tas de valeurs k des valeurs les plus élevées jusqu’ici. Le runtime serait O (n * logk). Vous pouvez appeler ce temps linéaire si k est une taille fixe et k << n.

    Je ne pense pas que la médiane soit possible cependant. Le simple fait de créer un segment de taille O (n) nécessite un temps O (n * logn).

    Edit: Ok, après y avoir réfléchi un peu plus, IVlad a raison. Vous pouvez créer un tas dans O (n), pour une taille fixe. Mais … cela n’aide pas l’OP avec sa question médiane. La technique de création de segment de mémoire linéaire produit uniquement un segment de mémoire valide en tant que résultat final. La méthode simple consistant à insérer n insère un segment de mémoire valide après chaque étape: O (n * logn).

    Il me semble que l’utilisation de tas pour trouver la médiane nécessiterait l’utilisation de sous-tas. Par exemple, il y avait une réponse postée ici (qui semble être maintenant supprimée), liée à un article de blog suggérant un algorithme pour résoudre ce problème. Il a suivi la médiane en cours d’exécution en utilisant deux tas (la plus petite moitié et la plus grande moitié) car il ne fait qu’un seul passage à travers les données. Cela nécessiterait une approche de tas plus lente et naïve, car cela dépend du maintien de tas valables pendant qu’il les insère et les enleve.

    Y a-t-il une autre façon de trouver la médiane en utilisant la technique de création de tas linéaire à un coup?