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