Python beginners organize heapsort

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 heap.png ~~ 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.

Recommended Posts

Python beginners organize heapsort
Python beginners organize quicksort
Python beginners organize bubble sort
Beginners practice Python
Python beginner's note
Python Beginner's Guide (Functions)
Python beginners touch Pytorch (3)
python textbook for beginners
Python Dictionary Beginner's Guide
Python beginners touch Pytorch (1)
Python beginners touch Pytorch (2)
Python Beginner's Guide (Introduction)
OpenCV for Python beginners
Organize types in Python
Learning flow for Python beginners
About python beginner's memorandum function
Python3 environment construction (for beginners)
Organize your Python development environment
3 Reasons Beginners to Start Python
Python #function 2 for super beginners
Python Beginner's Guide (Variables / Arrays)
Basic Python grammar for beginners
100 Pandas knocks for Python beginners
Python for super beginners Python #functions 1
Python #list for super beginners
~ Tips for beginners to Python ③ ~
Python
Python for super beginners Python # dictionary type 1 for super beginners
Machine learning summary by Python beginners
Python #index for super beginners, slices
Typing automation notes by Python beginners
<For beginners> python library <For machine learning>
Python #len function for super beginners
Beginners use Python for web scraping (1)
# 2 Python beginners challenge AtCoder! ABC085C --Otoshidama
Run unittests in Python (for beginners)
Memorandum of beginners Python "isdigit" movement
Beginners use Python for web scraping (4) ―― 1
Python #Hello World for super beginners
Python for super beginners Python # dictionary type 2 for super beginners
python beginners tried to find out
Learn the basics of Python ① Beginners
[Python] Minutes of study meeting for beginners (7/15)
Answer to AtCoder Beginners Selection by Python3
[Episode 2] Beginners tried Numeron AI with python
[Episode 3] Beginners tried Numeron AI with python
Memorandum of python beginners About inclusion notation
Let's put together Python for super beginners
Algorithm learned with Python 19th: Sorting (heapsort)
[Episode 0] Beginners tried Numeron AI with python
[Episode 1] Beginners tried Numeron AI with python
10 Python errors that are common to beginners
[Python] Read images with OpenCV (for beginners)
[Part1] Scraping with Python → Organize to csv!
Organize data divided by folder with Python
WebApi creation with Python (CRUD creation) For beginners
How Python beginners get started with Python with Progete
Atcoder standard input set for beginners (python)
[For beginners] Try web scraping with Python
A textbook for beginners made by Python beginners