This article example describes the Python sort search basic algorithm of heap sort. Shared for your reference, as follows:
Heap is a complete binary tree, heap sort is a kind of tree selection sort, using the characteristics of the top element of the big top of the heap is the largest, constantly take out the largest element, and adjust to make the rest of the elements or the big top of the heap, in order to take out the largest element is the sorted list. For example, the sequence [26,5,77,1,61,11,59,15,48,19] is sorted as follows:
The code for the heap-based priority queuing algorithm is as follows:
def fixUp(a): # Add new elements to the end of the heap, fixUp restores heap conditions
k=len(a)-1
while k>1 and a[k//2]<a[k]:
a[k//2],a[k]=a[k],a[k//2]
k=k//2
def fixDown(a): # Take the value returned by a[1] and move a[N] to a[1], fixDown to restore the condition of the heap
k=1
N=len(a)-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]:
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def insert(a,elem):
(elem)
fixUp(a)
def delMax(a):
maxElem=a[1]
N=len(a)
if N<=1:
print('There\'s none element in the list')
return -1
if N==2:
return a[1]
else:
a[1]=()
fixDown(a)
return maxElem
data=[-1,] # First element not used, placeholder
insert(data,26)
insert(data,5)
insert(data,77)
insert(data,1)
insert(data,61)
insert(data,11)
insert(data,59)
insert(data,15)
insert(data,48)
insert(data,19)
result=[]
N=len(data)-1
for i in range(N):
print(data)
(delMax(data))
print(result)
The fixUp function is used to add a new element to the tail of the list and then adjust it into the big top heap; the fixDown function is used to take out the largest element of the big top heap and then put the element at the tail of the list to the top of the heap and then adjust it into the big top heap; the insert function is used to insert a new element at a time and adjust it into the big top heap; and the delMax function is used to return the largest element and adjust the remaining elements into the big top heap.
The output is as follows:
[-1, 77, 61, 59, 48, 19, 11, 26, 1, 15, 5] [-1, 61, 48, 59, 15, 19, 11, 26, 1, 5] [-1, 59, 48, 26, 15, 19, 11, 5, 1] [-1, 48, 19, 26, 15, 1, 11, 5] [-1, 26, 19, 11, 15, 1, 5] [-1, 19, 15, 11, 5, 1] [-1, 15, 5, 11, 1] [-1, 11, 5, 1] [-1, 5, 1] [-1, 1] [77, 61, 59, 48, 26, 19, 15, 11, 5, 1]
The first output is the big top heap after constantly removing the largest element. Since it is a complete binary tree, you can write your own tree structure for the big top heap based on the list, so I won't go into it here, and the last line is a sorted list.
Here is the heap sort algorithm with the following code:
def fixDown(a,k,n): # top-down stacking, starting with k
N=n-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]: # Pick the bigger of the left and right child nodes
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def heapSort(l):
n=len(l)-1
for i in range(n//2,0,-1):
fixDown(l,i,len(l))
while n>1:
l[1],l[n]=l[n],l[1]
fixDown(l,1,n)
n-=1
return l[1:]
l=[-1,26,5,77,1,61,11,59,15,48,19] # First element not used, placeholder
res=heapSort(l)
print(res)
The output is as follows:
[1, 5, 11, 15, 19, 26, 48, 59, 61, 77]
PS: Here is another demo tool on sorting for your reference:
Online animated demonstration of insertion/selection/bubbling/merging/hill/fast sort algorithm process tool:
http://tools./aideddesign/paixu_ys
Readers interested in more Python related content can check out this site's topic: thePython Data Structures and Algorithms Tutorial》、《Summary of Python encryption and decryption algorithms and techniques》、《Summary of Python coding manipulation techniques》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniquesand thePython introductory and advanced classic tutorials》
I hope that what I have said in this article will help you in Python programming.