Implemented the algorithm of "Algorithm Picture Book" in Python3 (Heapsort)

About this article

In this article, I would like to introduce an implementation example in Python 3 about the algorithm that I learned by reading "Algorithm Picture Book". The algorithm this time is heapsort. The writer is an amateur. I would appreciate it if you could tell me various things.

I'm not familiar with Python2, but I only know that I'm using Python3 (Is it Python3.6.0?). Therefore, the title of the article is Python3.

About heapsort

I will only briefly explain the problem setting and approach. It uses a data structure called a "heap". For details on the heap, refer to "Algorithm Picture Book".

problem

Returns the columns sorted by the smallest number for a given number of columns.

Example: 5, 2, 7, 3, 6, 1, 4 → 1, 2, 3, 4, 5, 6, 7

approach

Store the given number in the descending heap (the root is the largest), and repeat "take the value from the root → put it on the leftmost". See "Algorithm Picture Book" for details.

Implementation code and execution result

The implemented code is shown below. First, I will explain a little idea.

In addition, I dared to implement it for study, but Python seems to have a module called heapq in the standard library, so I think that it is good to use it practically (https://docs.python) .org / ja / 3 / library / heapq.html).

Way of thinking

A data structure called a heap is realized by assuming the meaning in the order of the elements of the array. I think it will be easier to understand if you look at the supplement in the heapsort section of the "Algorithm Picture Book".

Also, for heaps (binary heaps), it is convenient to start the element number with 1, so do so (Wikipedia binary heap # heap implementation % 8C% E5% 88% 86% E3% 83% 92% E3% 83% BC% E3% 83% 97 #% E3% 83% 92% E3% 83% BC% E3% 83% 97% E3% 81% AE% E5% AE% 9F% E8% A3% 85))).

Roughly speaking, it looks like the following.

--Store the values in the array heap --Ignore heap [0](put a dummy value) --heap [1] is the root --heap [2] and heap [3] are children of heap [1], heap [4] and heap [5] are children of heap [2], heap [6] and heap [7] are children of heap [3] Child,...

code

The list assigned to the variable data first is the column of the number to be processed.

Also, this code can be confusing, so I'll add a supplementary version of the (?) Version of the code that defines some functions and gives a better view at the bottom. We would appreciate it if you could give us your opinion on which one is better.

heap_sort.py


data = [5, 2, 7, 3, 6, 1, 4]

print("input    :" + str(data))
data_len = len(data)

heap = [0] #The 0th element is a dummy(Counting from 1 on the heap makes it easier to calculate)

#Store the input data in the heap in order(Rebuild the heap each time)
for i in range(0, data_len):
    heap.append(data[i])
    if i > 0:
        child = i + 1
        parent = child // 2
        while(heap[parent] < heap[child]):
            heap[parent], heap[child] = heap[child], heap[parent]
            if parent > 1:
                child = parent
                parent = child // 2
            else:
                #It has reached the root, so I will exit here
                break

#Fetch values from the root of the heap(Rebuild the heap each time)
output_data = list() #Array for output

for i in range(0, data_len):
    #Copy root value
    output_data.insert(0, heap[1])

    #Remove root values and rebuild heap
    heap[1] = heap[-1]
    heap.pop(-1)

    parent = 1
    while(len(heap) >= 2 * parent + 1):
        if len(heap) == 2 * parent + 1:
            if heap[parent] < heap[2 * parent]:
                heap[parent], heap[2 * parent] = heap[2 * parent], heap[parent]
            #There are no branches beyond this, so it will come out
            break
        else:
            if heap[2 * parent] > heap[2 * parent + 1]:
                child = 2 * parent
            else:
                child = 2 * parent + 1
            if heap[parent] < heap[child]:
                heap[parent], heap[child] = heap[child], heap[parent]
                parent = child
            else:
                break

print("output   :" + str(output_data))


Execution result

python


$ python heap_sort.py 
input    :[5, 2, 7, 3, 6, 1, 4]
output   :[1, 2, 3, 4, 5, 6, 7]

At the end

If you have any questions, please point out and ask questions. Especially if there are any improvements in how to write the code, I think it will be useful for studying.

Also, I would appreciate any hints on testing the implementation code and comparing the speed with other algorithms. (I haven't tested it yet (^^;)

Supplement

This is the (?) Version of the code above that has improved visibility by defining some functions.

heap_sort_2.py


def parent_of(child):
    return child // 2

def left_child_of(parent):
    return 2 * parent

def right_child_of(parent):
    return 2 * parent + 1

def heap_size(heap):
    return len(heap[1:])

data = [5, 2, 7, 3, 6, 1, 4]
# data = [43, 1, -4, 91, 46, -609]

print("input    :" + str(data))
data_len = len(data)

heap = [0] #The 0th element is a dummy(Counting from 1 on the heap makes it easier to calculate)

#Store the input data in the heap in order(Rebuild the heap each time)
for i in range(0, data_len):
    heap.append(data[i])
    if i > 0:
        child = i + 1
        parent = parent_of(child)
        while(heap[parent] < heap[child]):
            heap[parent], heap[child] = heap[child], heap[parent]
            if parent > 1:
                child = parent
                parent = parent_of(child)
            else:
                #It has reached the root, so I will exit here
                break

#Fetch values from the root of the heap(Rebuild the heap each time)
output_data = list() #Array for output

for i in range(0, data_len):
    #Copy root value
    output_data.insert(0, heap[1])

    #Remove root values and rebuild heap
    heap[1] = heap[-1]
    heap.pop(-1)

    parent = 1
    while(heap_size(heap) >= left_child_of(parent)):
        if heap_size(heap) == left_child_of(parent):
            child = left_child_of(parent)
            if heap[parent] < heap[child]:
                heap[parent], heap[child] = heap[child], heap[parent]
            #There are no branches beyond this, so it will come out
            break
        else:
            if heap[left_child_of(parent)] > heap[right_child_of(parent)]:
                child = left_child_of(parent)
            else:
                child = right_child_of(parent)
            if heap[parent] < heap[child]:
                heap[parent], heap[child] = heap[child], heap[parent]
                parent = child
            else:
                break

print("output   :" + str(output_data))

Recommended Posts

Implemented the algorithm of "Algorithm Picture Book" in Python3 (Heapsort)
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Bubble Sort)
Implemented the algorithm of "Algorithm Picture Book" in Python3 (selection sort)
Picture book data structure algorithm Python
Check the behavior of destructor in Python
Ant book in python: Sec.2-5 Dijkstra's algorithm
The result of installing python in Anaconda
The basics of running NoxPlayer in Python
In search of the fastest FizzBuzz in Python
What kind of book is the best-selling "Python Crash Course" in the world?
Output the number of CPU cores in Python
[Python] Sort the list of pathlib.Path in natural sort
Get the caller of a function in Python
Match the distribution of each group in Python
View the result of geometry processing in Python
Make a copy of the list in Python
Find the solution of the nth-order equation in python
The story of reading HSPICE data in Python
[Note] About the role of underscore "_" in Python
About the behavior of Model.get_or_create () of peewee in Python
Solving the equation of motion in Python (odeint)
Output in the form of a python array
I implemented the inverse gamma function in python
Implemented SimRank in Python
Genetic algorithm in python
Algorithm in Python (Bellman-Ford)
Implemented Shiritori in Python
Algorithm in Python (Dijkstra's algorithm)
[Fundamental Information Technology Engineer Examination] I wrote the algorithm of Euclidean algorithm in Python.
Experience the good calculation efficiency of vectorization in Python
Sort in Python. Next, let's think about the algorithm.
Basic information Write the 2018 fall algorithm problem in Python
[python] Get the list of classes defined in the module
The story of FileNotFound in Python open () mode ='w'
Implement the solution of Riccati algebraic equations in Python
Get the size (number of elements) of UnionFind in Python
Not being aware of the contents of the data in python
Reproduce the execution example of Chapter 4 of Hajipata in Python
Let's use the open data of "Mamebus" in Python
[Python] Outputs all combinations of elements in the list
Get the URL of the HTTP redirect destination in Python
A reminder about the implementation of recommendations in Python
Reproduce the execution example of Chapter 5 of Hajipata in Python
To do the equivalent of Ruby's ObjectSpace._id2ref in Python
Check the asymptotic nature of the probability distribution in Python
Towards the retirement of Python2
Download the file in Python
Find the difference in Python
Algorithm in Python (primality test)
About the ease of Python
Equivalence of objects in Python
Reproduce Euclidean algorithm in Python
Algorithm in Python (binary search)
Sudoku solver implemented in Python 3
Implement Dijkstra's Algorithm in python
Implementation of quicksort in Python
About the features of Python
6 Ball puzzle implemented in python
The Power of Pandas: Python
Try scraping the data of COVID-19 in Tokyo with Python
Find out the apparent width of a string in python