Les propriétés du tas
Un tas est un arbre complètement binaire, qui peut être mis en œuvre dans la réalité via un tableau. L'une de ses propriétés les plus importantes est que tout nœud est plus petit que (supérieur à) est égal à ses nœuds enfants. Le tas avec le plus petit nœud racine est appelé le plus petit tas, et le tas avec le plus grand nœud racine est appelé le plus grand tas. La figure suivante montre un exemple d'un plus grand tas et de sa représentation de tableau, qui peut être constaté intuitivement que chaque nœud est plus grand que ses enfants.
Comme le montre la figure ci-dessus, les nœuds d'un arbre complètement binaire peuvent être disposés dans l'ordre dans le nœud racine numéro 1, correspondant à l'index dans le tableau A (notez que l'indice ici commence à partir de 1). Étant donné un nœud I, nous pouvons facilement obtenir son enfant gauche est 2i, l'enfant droit est 2i + 1, et le nœud parent est i / 2
Opérations de base de tas
Il existe deux opérations de base pour le tas (voir le tas minimum comme exemple ci-dessous):
Insérez l'élément K: Ajoutez K directement à l'extrémité du tableau, puis bouillonnez pour régler le tas. Fonctionnement de bulle: Comparez l'élément à ajuster à son nœud parent, et s'il est supérieur à son nœud parent, échangez-le jusqu'à ce que les propriétés du tas soient restaurées.
Extraire le plus de valeur: le plus de valeur est l'élément racine. Ensuite, supprimez-le, laissez l'élément racine = l'élément du dernier nœud de feuille, puis bulle à partir de l'élément racine pour ajuster le tas. Opération de bulle: chaque fois, vous devez sélectionner le plus petit nœud enfant dans les trois nœuds pour ajuster le nœud, qui a les enfants gauche et droit à échanger (si le plus petit, il n'a pas besoin de se échanger), jusqu'à ce que les propriétés du tas soient restaurées.
En pratique, il est souvent nécessaire de construire un tableau non ordonné contenant des éléments n en tas. Le constructeur de la classe de tas ci-dessous montrera comment construire un tas via le réglage de la bulle _bubblenown. Le tas est essentiellement un arbre complètement binaire, et la hauteur de l'arbre est toujours lognlogn. Le fonctionnement long de chaque opération de base consiste à bouillonner et à s'adapter pour répondre aux propriétés du tas, donc leur complexité temporelle est O (nlogn) o (nlogn).
Exemple de Java:
// float public void natan (int k) {while (k / 2> = 1 && moins (pq [k / 2], pq [k])) {échange (pq, k / 2, k); k = k / 2; }} // snime private void swier () {int k = 1; while (2 * k <n) {int j = 2 * k; if (moins (pq [j], pq [j + 1])) j ++; if (moins (pq [k], pq [j])) échange (pq, k, j); d'autre se casse; k = j; }} Principe de mise en œuvre du tri de tas
Il est divisé en deux étapes:
1. Arrachez les tableaux dans l'ordre du tas binaire
2. Changez la position du nœud racine et du dernier nœud, puis coulez le nœud racine.
accomplir:
Peut-être que mon code est légèrement différent de l'animation ci-dessus, mais les principes de base sont similaires.
classe publique Heapsort étend Basesort {private int n; @Override public void tri (comparable [] a) {n = a.Length-1; int k = n / 2; tandis que (k> = 1) {swier (a, k); K--; } k = 1; tandis que (k <= n) {échange (a, k, n--); puits (a, k); }}}