Comment trouver la médiane des nombres en temps linéaire à l'aide de tas?

Question

Wikipedia dit:

Algorithmes de sélection: il est possible de rechercher les éléments min, max, min et max, médian ou même le k-ème plus grand élément en temps linéaire à l'aide de tas.

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

Pouvez-vous m'expliquer comment cela peut être fait en utilisant des tas?

Answer 1

Vous pouvez utiliser un min-max médiane tas pour trouver le minimum, maximum et médiane de la constante de temps (et de prendre le temps linéaire pour construire le tas). Vous pouvez utiliser la commande-statistiques des arbres pour trouver le k-ième plus petit/plus grand valeur. Ces deux structures de données sont décrites dans le présent document de min-max des tas [lien pdf]. Min-max des tas binaires tas qui alternent entre min-tas-max-tas.

Le papier: Un min-max médiane tas est un tas binaire, avec les propriétés suivantes:

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

2) Le sous-arbre gauche de la racine est un min-max tas Hl de la taille de plafond[((n-1)/2)] contenant des éléments est inférieure ou égale à la médiane. Le sous-arbre droit est un max-min tas Rh de la taille de l'étage[((n-1)/2)] ne contenant que des éléments supérieure ou égale à la médiane.

Le document explique comment construire un segment de mémoire.

Edit: en lisant le papier de manière plus approfondie, il semble que la construction du min-max médiane des tas nécessite tout d'abord de trouver la médiane (FTA: "Trouver la médiane de l'ensemble de n éléments à l'aide de tout l'un de l'linéaire connue algorithmes temps"). Cela dit, une fois que vous avez construit le tas, vous pouvez maintenir la médiane simplement par le maintien de l'équilibre entre le min-max tas sur la gauche et le max-min tas sur la droite. DeleteMedian remplace la racine avec le min max-min tas ou le max du min-max tas (selon le maintient de l'équilibre).

Donc, si vous prévoyez sur l'utilisation d'un min-max médiane tas pour trouver la médiane d'un fixe de l'ensemble de données, vous êtes SOL, mais si vous l'utilisez sur l'évolution de l'ensemble de données, il est possible.

Answer 2

Voir cette page de wikipédia sur les algorithmes de sélection. En particulier, regardez la BFPRT algorithme et la Médiane des Médianes de l'algorithme. BFPRT est de manière probabiliste linéaire, et est calqué sur celui de quicksort; Médiane des Médianes est garanti linéaire, mais a un grand facteur constant et donc, peut prendre plus de temps dans la pratique, en fonction de la taille de votre jeu de données.

Si vous n'avez que quelques centaines ou quelques milliers d'éléments à sélectionner la médiane, je soupçonne qu'un simple quicksort suivi en direct de l'indexation est le plus simple.

Answer 3

Il y a probablement de meilleurs algorithmes, mais voici comment je ferais:

Deux seaux et d'une valeur. La valeur est la médiane, les deux compartiments sont "plus grande que la médiane" et "plus petit que" médiane. Pour chaque élément, x dans le tableau, rééquilibrer les seaux tels que big_bucket et small_bucket diffèrent pas de plus de 1 dans leur taille. Lorsque vous déplacez des éléments de la grand seau pour le petit seau d'abord, ils doivent passer par la valeur médiane pour y arriver (c'est une différence de 2 va réussir à pousser un élément d'un seau à l'autre -, une différence de 1 de pousser un élément à partir d'un seau à la valeur médiane.) À la fin de votre premier passage à travers le tableau de la valeur à votre médiane.

Answer 4

peut-être qu'il n'était pas là quand la question initiale a été posée, mais maintenant wiki a un lien vers la source, et c'est ici: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

plus précisément, allez à la page 17, et de regarder la description de RSEL4. Ils sont la preuve de théorème 3.2 que le temps de la complexité de ce k-ième de sélection de l'algorithme est O(k). il suffirait de vous O(n) pour construire le tas, et un supplément de O(k) pour trouver le k-ième plus petit élément.

ce n'est pas vraiment aussi simple que certains des autres réponses ont suggéré

Answer 5

Mon exécutable Java mise en œuvre de l'algorithme de sélection, qui permet de sélectionner le k-ième plus petit élément d'un tableau donné en garantie en temps linéaire.

https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/array/KthElementSelection.java