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.
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".
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
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.
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).
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,...
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))
python
$ python heap_sort.py
input :[5, 2, 7, 3, 6, 1, 4]
output :[1, 2, 3, 4, 5, 6, 7]
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 (^^;)
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