# Dahua algorithm sort heap sort

Heap sorting: large root heap requires that the value of each node is less than or equal to the value of the parent node, while small root heap requires that the value of each node is greater than or equal to the value of the parent node
1. Parent node list[i] left node list[2i+1] right node list[2i+2]
2. List [i] > = list [2I + 1] & & list [i] > = list [2I + 2]
3. List [i] < = list [2I + 1] & & list [i] < = list [2I + 2]
In the data structure of the heap, the maximum value in the heap is always at the root node (the minimum value in the heap used in the priority queue is at the root node). The following operations are defined in the heap:

1. Max heap adjustment: adjust the end terminal node of the heap so that the child node is always smaller than the parent node

2. Create a Build Max Heap: reorder all data in the heap

3. HeapSort: remove the root node of the first data and perform recursive operation of maximum heap adjustment

python implementation algorithm:

```# Insert data into a heap that has already been built
def heap_insert(data, index):
# If the current data is larger than its parent node, exchange it, and then continue to compare it with its parent node
root = int((index - 1) / 2)
while data[index] > data[root]:
data[index], data[root] = data[root], data[index]
index = root
root = int((index - 1) / 2)

# When a number in a big pile becomes smaller, it sinks
def heapify(data, index, length):
left = index * 2 + 1
while left < length:
right = left + 1
# Compare the left and right child nodes of the current node to find the largest subscript
larger = right if (right < length and data[right] > data[left]) else left
# Compare the largest one between the current node and the child node, and find the subscript of the larger one
larger = larger if data[larger] > data[index] else index
# If the current node and the maximum number of nodes are the same, no action is required
if larger == index: break
# The largest switch between the current node and the left and right nodes
data[larger], data[index] = data[index], data[larger]
# The current node points to the largest node, then continue to judge
index = larger
left = index * 2 + 1

def heapsort(data):
size = len(data)
if not data or size < 2:
return data
# Create a large root heap
for i in range(size):
heap_insert(data, i)

size -= 1
# Then adjust the heap to a large one
while size > 0:
data[0], data[size] = data[size], data[0]
heapify(data, 0, size)
size -= 1
return data
#Generate random list
def random_data():
import random
res = []
for i in range(random.randint(1, 100)):
res.append(random.randint(1, 100))
return res

#Logarithmic device
def compare(src, res):
data = sorted(src)
if len(data) == len(src):
for i in range(len(data)):
if data[i] != res[i]:
return False
return True

if __name__ == '__main__':
for i in range(100000):
src = random_data()
des = heapsort(src)
if not compare(src, des):
print(src)```

Tags: Python less

Posted on Sat, 30 Nov 2019 20:23:32 -0800 by andybrooke