This is a memorandum

I haven't touched it at all since I got the basic information, so what about heapsort? I thought I would take notes while organizing my knowledge.

Pakuru I will quote

It's not impossible to create an algorithm from scratch, but honestly it's tough, so I quoted it from the [Reference: A] site and myself. I will organize it while disassembling it with.

What is heapsort in the first place?

I wrote down the general rules with an image ~~ I don't know why I thought about such a complicated thing, but ~~ It seems that it is easy to operate up and down due to the operation of the array. It seems that the tree structure is also used in Oracle DB (remember), and the data search efficiency seems to be good.

I wrote it in a special note because I think there are three points to remember.

Body

A function of the heapsort body. If you put an array as an argument here, it will be sorted

`heap_sort.py`


def heap_sort(array):
    i = 0
    n = len(array)
    #Configure heap
    while(i < n):
        upheap(array, i)
        i += 1
    while(i > 1):#From n to 0
        #Fetch the maximum value from the heap
        i -= 1
        array[0] , array[i] = array[i] , array[0]
        
        #Heap reconstruction
        downheap(array, i-1)

When you receive the array, define the length and index (as usual).

Then, while passing the index to upheao, it loops from 0 to the last.

Maybe I would write for i in range (len (array)). I only use n or here. Is it hard to read? ~~ Shiranai ~~

And a downheep loop. Honestly, the reason I decided to write this article. ~~ It's hard to understand ~~

By the way, array[0] , array[i] = array[i] , array[0] Is a swap. It seems that python can write like this, so I tried it. Justice is enough for one line.

What is upheap?

upheap accepts arrays and indexes as arguments. It receives array and i from the body. By the way, while n means while n! = 0. If it's not 0, it's true.

`upheap.py`


def upheap(array, n):
    while n:
        parent = int((n - 1) / 2)
        #Try to take the value of parent> child
        if array[parent] < array[n]:
            array[n] , array[parent] = array[parent] , array[n]
            n = parent
        else:
            break

This is the task of passing a small number to the child. The heap is basically a rule that "parents are small, children are large", so if you do not do this once, you will not be able to pass large numbers to children. So, once you pass a large number to the top (parent side), prepare to pass a large number to the child.

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]

It will be sorted like this

What is downheep?

downheap accepts arrays and indexes as arguments. It receives array and i-1 from the body.

`downheap.py`


#root[0]The heap(0～n)Move to the optimum position
def downheap(array, n):
    if n==0: return
    parent = 0
    while True:
        child = 2 * parent + 1 # array[n]Child element of
        #When you go out of the element, brake
        if child > n:
            break
        #If there is a child next to you and left <right, look at the child on the right
        if (child < n) and array[child] < array[child + 1]:
            child += 1
        #Swap if parent is smaller than child
        if array[parent] < array[child]: 
            array[child] , array[parent] = array[parent] , array[child]
            
            parent = child; #Retains index after replacement
        else:
            break

I've added a lot of annotations, but isn't it still difficult to understand? As a prerequisite, before entering this function array[0] , array[i] = array[i] , array[0] doing. (I is the focused part) By doing this, the highest number is passed to the lowest child before sorting, and the largest number to be passed next is brought to the highest parent. Can be said

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]

Do you see that as the focus index goes higher, the sorted numbers accumulate in the lower data? This will give you a nice sort.

Finally

This time, I was organizing the algorithm while writing an article, but I made a lot of mistakes, so I traced and repeated the confirmation so that my explanation was as correct as possible. This kind of form is a study, so I hope I can continue with self-satisfaction.

reference

[Reference: A] https://webbibouroku.com/Blog/Article/py-heapsort ~~ Marupaku ~~ I quoted it. I think that the head family gives a more accurate explanation, so if you don't like something that is chewed poorly, please understand it at the head family.

[GO] Python beginners organize heapsort