Algorithm learned with Python 19th: Sorting (heapsort)

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. Heapsort is handled as the 19th bullet.

Heapsort

For the stack and queue handled last time, heapsort handles data by a tree structure called heap. There are no restrictions on the heap between child nodes, but there are restrictions on the magnitude relationship between the parent node and the child nodes. In some cases (Parent $ \ le $ child), (parent $ \ ge $ child). This time, the constraint is (parent $ \ le $ child) in order to handle data from the smallest one. The image is shown below.

A heap with a structure of two child nodes for one parent node is called a ** binary heap **. Drop the list data into this heap structure as we have dealt with. At this time, it can be seen that dropping into the heap structure means that the values ​​are smaller in order from the top of the tree. That is, ** If you retrieve the top parent node, you will get the minimum value at that time **. The situation is shown below. As shown in the figure, the binary tree collapses. At that time, the end temporarily moves to the top to supplement the binary tree structure. However, inevitably, the constraints of the parent node and the child node are often not satisfied. In heapsort, in order to always maintain the heap structure, the heap structure is arranged again according to the constraints. The situation is shown below. Even after this heap structure is modified, it is shown below. From the above figure, it can be seen that the heap is configured again and the minimum value at that time is in the top parent node. By repeating this operation, the items are sorted in ascending order.

Here, the correspondence between the list and the heap is shown below.

Implementation

The code using the Python standard library and the output at that time are shown below.

code

heap_sort.py

"""
2021/01/16
@Yuya Shimizu

Heapsort
"""
import heapq    #Python standard library that handles the heap

def heap_sort(data):
    DATA_FOR_HEAP = data.copy()     #Stores data to create a heap
    heapq.heapify(DATA_FOR_HEAP)    #Heap generation (tree structure arranged in minimum order)
    return [heapq.heappop(DATA_FOR_HEAP) for _ in range(len(data))] #Extract in order with heappop function

if __name__ == '__main__':
    DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]

    sorted_data = heap_sort(DATA)

    print(f"{DATA} → {sorted_data}")

output

[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

Computational complexity

In stacks and queues, the amount of calculation is $ O (n ^ 2) $ in order notation, but in heapsort, the amount of calculation is ** $ O (log (n)) $ **. It can be seen that the amount of calculation does not increase so much even when the number of $ n $ (the number of data) increases.

Impressions

A method of describing an algorithm by making full use of recursion without using the standard library was also introduced, but it is omitted here. I understand the algorithm, and if Python has a standard library, I think I should use it. Since I understand the algorithm itself, I think that if necessary, I should return to the algorithm again at that time. The rest are merge sort and quick sort, and the end of the sorting algorithm is visible. I'm looking forward to the next time.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha