Ceci est un mémorandum

Je n'y ai pas touché du tout depuis que j'ai les informations de base, alors qu'en est-il du tri en tas? J'ai pensé que je prendrais des notes tout en organisant mes connaissances.

Pakuru Je vais citer

Il n'est pas impossible de créer un algorithme à partir de zéro, mais honnêtement, c'est difficile, alors je l'ai cité sur le site [Reference: A] et moi-même. Je vais l'organiser en le démontant avec.

Qu'est-ce que le tri par tas en premier lieu?

J'ai écrit les règles générales avec une image ~~ Je ne sais pas pourquoi j'ai pensé à une chose aussi compliquée, mais ~~ Il semble qu'il soit facile de faire fonctionner de haut en bas en raison du fonctionnement de l'arrangement. Il semble que la structure arborescente soit également utilisée dans Oracle DB (rappelez-vous), et l'efficacité de la recherche de données semble bonne.

Je l'ai écrit dans une note spéciale parce que je pense qu'il y a trois points à retenir.

Corps

Une fonction du corps de tri de tas. Si vous mettez un tableau comme argument ici, il sera trié

`heap_sort.py`


def heap_sort(array):
    i = 0
    n = len(array)
    #Configurer le tas
    while(i < n):
        upheap(array, i)
        i += 1
    while(i > 1):#De n à 0
        #Récupérer la valeur maximale du tas
        i -= 1
        array[0] , array[i] = array[i] , array[0]
        
        #Reconstruire le tas
        downheap(array, i-1)

Lorsque vous recevez le tableau, définissez la longueur et l'index (comme d'habitude).

Ensuite, tout en passant l'index à upeao, exécutez la boucle de 0 à la dernière.

Peut-être que j'écrirais for i in range (len (array)). Je n'utilise que n ou ici. Est-ce difficile à lire? ~~ Shiranai ~~

Et une boucle descendante. Honnêtement, la raison pour laquelle j'ai décidé d'écrire cet article. ~~ C'est difficile à comprendre ~~

Au fait, array[0] , array[i] = array[i] , array[0] Est-ce un échange. Il semble que python puisse écrire comme ça, alors je l'ai essayé. Une seule ligne suffit.

Qu'est-ce que monter?

upeap accepte les tableaux et les index comme arguments. Il reçoit array et i du corps. Au fait, «while n» signifie «tandis que n! = 0». Si ce n'est pas 0, c'est vrai.

`upheap.py`


def upheap(array, n):
    while n:
        parent = int((n - 1) / 2)
        #Essayez de prendre la valeur de parent> enfant
        if array[parent] < array[n]:
            array[n] , array[parent] = array[parent] , array[n]
            n = parent
        else:
            break

C'est la tâche de transmettre un petit nombre à l'enfant. Le tas est fondamentalement une règle selon laquelle "les parents sont petits, les enfants sont grands", donc si vous ne le faites pas une fois, vous ne pourrez pas transmettre un grand nombre aux enfants. Ainsi, une fois que vous passez un grand nombre vers le haut (côté parent), préparez-vous à transmettre un grand nombre à l'enfant.

before [1, 2, 3, 4, 5, 3, 2, 1, 4, 3, 4, 5, 0] upheap [5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0]

Il sera trié comme ça

Qu'est-ce que Downheep?

downheap prend un tableau et un index comme arguments. Il reçoit le tableau et i-1 du corps.

`downheap.py`


#racine[0]Le tas(0～n)Déplacer vers la position optimale
def downheap(array, n):
    if n==0: return
    parent = 0
    while True:
        child = 2 * parent + 1 # array[n]Élément enfant de
        #Sortez de l'élément
        if child > n:
            break
        #S'il y a un enfant à côté de vous et à gauche <à droite, regardez l'enfant à droite
        if (child < n) and array[child] < array[child + 1]:
            child += 1
        #Swap si le parent est plus petit que l'enfant
        if array[parent] < array[child]: 
            array[child] , array[parent] = array[parent] , array[child]
            
            parent = child; #Conserve l'index après le remplacement
        else:
            break

J'ai ajouté beaucoup de notes, mais n'est-ce pas encore difficile à comprendre? Comme condition préalable, avant d'entrer dans cette fonction array[0] , array[i] = array[i] , array[0] Faire. (Je suis la partie focalisée) Ce faisant, le nombre le plus élevé est transmis à l'enfant le plus bas avant le tri, et le plus grand nombre à transmettre ensuite est amené au parent le plus élevé. Peut être dit

before[1,2,3,4,5,3,2,1,4,3,4,5,0] upheap[5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0] [5, 4, 3, 4, 4, 2, 2, 1, 1, 3, 3, 0, 5] [4, 4, 3, 1, 4, 2, 2, 0, 1, 3, 3, 5, 5] [4, 4, 3, 1, 3, 2, 2, 0, 1, 3, 4, 5, 5] [4, 3, 3, 1, 3, 2, 2, 0, 1, 4, 4, 5, 5] [3, 3, 3, 1, 1, 2, 2, 0, 4, 4, 4, 5, 5] [3, 1, 3, 0, 1, 2, 2, 3, 4, 4, 4, 5, 5] [3, 1, 2, 0, 1, 2, 3, 3, 4, 4, 4, 5, 5] [2, 1, 2, 0, 1, 3, 3, 3, 4, 4, 4, 5, 5] [2, 1, 1, 0, 2, 3, 3, 3, 4, 4, 4, 5, 5] [1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5] [1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5] [0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]

Voyez-vous que lorsque l'indice de mise au point augmente, les nombres triés s'accumulent dans les données inférieures? Cela vous donnera un bon tri.

finalement

Cette fois, j'organisais les algorithmes en écrivant un article, mais j'ai fait beaucoup d'erreurs, j'ai donc tracé et vérifié pour que mon explication soit la plus correcte possible. Ce type de formulaire est une étude, j'espère donc pouvoir continuer avec l'auto-satisfaction.

référence

[Référence: A] https://webbibouroku.com/Blog/Article/py-heapsort ~~ Marupaku ~~ Je l'ai cité. Je pense que le chef de famille donne une explication plus précise, donc si vous n'aimez pas quelque chose qui est mal mâché, veuillez le comprendre au chef de famille.

[GO] Les débutants en Python organisent des tris de tas