Article From:https://www.cnblogs.com/simple-free/p/9219171.html

#I still don’t feel clear enough.

(1)heap

The heap here refers to a heap data structure, not a garbage collector in Java. Heap can be understood as an approximately complete two binary tree. As shown below, the tree is fully filled except for the lowest level, and is filled from left to right. (at the bottom, it’s not filled, not filled).

For example: [5, 7, 8, 10, 12, 15] (small top pile)

(Two)The nature of the heap

The definition of heap in software designer test data should be satisfied with the following formula.

 

(Three)The process of heap sorting

 It is divided into 2 processes:

1、      Set up a large heap or a small heap. (simply put the list in line with the formula listed above).

2、      Sorting large or small top heaps

(Four)Set up a large heap(Understand the big top pile, small top pile almost, you can try to achieve it, you may write it more clearly.

From the second point, we know that to build a big top pile, we need to maintain the following properties.

 

For example, [15, 12, 10, 8, 7, 5] satisfy the above properties. Here we will start with the index from 1 instead of 0.

Implementation code:

 1 #Building pile
 2 def buildHeap(A):
 3     #The first insertion of a X here is to facilitate the comparison (since the index of the python list starts from 0) to facilitate the maintenance of the heap properties (Ki > = K2i and Ki > = K2i+1).
 4     #For example, the incoming list is [12,5,7,8,10,15], and here it becomes ['X', 12,5,7,8,10,15].
 5     #So the data we need to process is actually A[1], A[2]... A[n].
 6     #This'X'will never be used. The only function is to get the data we need to process from A[1].
 7     A.insert(0,'X')
 8     #Gets the index of the middle element of the list, which is reduced by 1 because of the addition of one element.
 9     k = (len(A)-1)//2
10     #This range (k, 0, -1) means I = k, I = k-1... (minimum 1, not equal to 0).
11     for i in range(k,0,-1):
12         maxHeap(A,i)
13     return A
14 #Maintenance of the properties of the big heap
15 def maxHeap(A,i):
16     #In order to maintain Ki > = K2i and Ki > = K2i+1, first get the corresponding index (subscript).
17     largest = i
18     k1 = 2*i
19     k2 = 2*i+1
20     #First condition: add this condition here because 2I may be greater than the list length when calling maxHeap recursively.
21     # In debug mode, the execution process of the function is clear.
22     #The second condition is to compare the size (corresponding to the formula, if Ki < K2i).
23     if k1 < len(A) and A[i] < A[k1]:
24         largest = k1
25     if k2 < len(A) and A[largest] < A[k2]:
26         largest = k2
27     #The condition is established to exchange data. It does not establish that A[i] is the largest.
28     if largest != i:
29         #Exchange the value of A[i] A[largest]
30         A[i],A[largest] = A[largest],A[i]
31         #After exchanging data, the subtree whose root is the node may violate the nature of the big top stack, so it calls itself recursively.
32         maxHeap(A,largest)

(Five)Sort the big heap

The process of sorting is to repeat the 1, 2, and 3 steps on the basis of a big heap (please note here that the first element of our list is’ X ‘, and the data to be processed is started from A[1]).

1、Exchange A[1] A[len (A) -1]. (it is to exchange the first and last data of the list, because the top data is exchanged before the exchange, and the last data of the list is the largest.

2、Delete the data at the end of the list and add it to the result list.

3、After data exchange, the nature of the big top stack is certainly not established. So call maxHeap () to maintain the nature of the big heap

 1 #Heap sorting
 2 def heapSort(A):
 3     # Here is a big heap back.
 4     A = buildHeap(A)
 5     #pythonThe index of the list starts from 0, so the index of the last element is the index after -1.
 6     k = len(A)-1
 7     result = []
 8     while k >0:
 9         #Exchange A[1] and A[k]
10         A[1],A[k]= A[k],A[1]
11         #Delete the data at the end of the A list and add it to the result list.
12         result.insert(0,A.pop())
13         # result.append(A.pop())
14         k -= 1
15         maxHeap(A,1)
16     return result

(Six)Complete code

 1 #Building pile
 2 def buildHeap(A):
 3     #The first insert of an element is convenient for comparison
 4     A.insert(0,'X')
 5     k = (len(A)-1)//2
 6     for i in range(k,0,-1):
 7         maxHeap(A,i)
 8     return A
 9 #Maintenance of the properties of the big heap
10 def maxHeap(A,i):
11     largest = i
12     k1 = 2*i
13     k2 = 2*i+1
14     if k1 < len(A) and A[i] < A[k1]:
15         largest = k1
16     if k2 < len(A) and A[largest] < A[k2]:
17         largest = k2
18     if largest != i:
19         A[i],A[largest] = A[largest],A[i]
20         #After exchanging data, the subtree whose root is the node may violate the nature of the big top stack, so it calls itself recursively.
21         maxHeap(A,largest)
22 #Heap sorting
23 def heapSort(A):
24     A = buildHeap(A)
25     k = len(A)-1
26     result = []
27     while k >0:
28         A[1],A[k]= A[k],A[1]
29         result.insert(0,A.pop())
30         # result.append(A.pop())
31         k -= 1
32         maxHeap(A,1)
33     return result
34 
35 B = [12,5,7,8,10,15]
36 
37 print(heapSort(B))

Leave a Reply

Your email address will not be published. Required fields are marked *