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)