This article example describes Python implementation of the heap sort algorithm based on the binary tree storage structure. Shared for your reference, as follows:
Now that I've implemented a binary tree in Python, of course I need to write something to practice.
There are a lot of tutorials on heap sorting on the web, but yet almost all of them store the numbers in arrays and access the elements directly from the subscripts, which is of course perfectly fine, simple to implement, fast to access, and easy to understand.
But for the sake of practicing, I wrote a heap sort of the binary tree storage structure
One of the most difficult problems is swapping two nodes in a binary tree.
Since a node is connected to at most three nodes, then two nodes swapped would need to take into account the relationship between the five nodes, and would also need to determine if they are left or right children, which would be very tedious and error prone.
class Tree:
def __init__(self, val = '#', left = None, right = None):
= val
= left
= right
= None
= None
= 0
#Precedence construction of binary trees
def FrontBuildTree(self):
temp = input('Please Input: ')
node = Tree(temp)
if(temp != '#'):
= ()
= ()
return node# Since there's no reference and no pointer, just give the new node back
# Pre-order traversal of a binary tree
def VisitNode(self):
print()
if( != None):
()
if( != None):
()
# Middle-order traversal of a binary tree
def MVisitTree(self):
if( != None):
()
print()
if( != None):
()
# Get the dec node of the binary tree
def GetPoint(self, dec):
road = str(bin(dec))[3:]
p = self
for r in road:
if (r == '0'):
p =
else:
p =
#print(' = ', )
return p
# Build the first heap
def BuildHeadTree(self, List):
for val in List:
#print('val = ', val, ' = ', )
= (int(( + 1) / 2))
#print(' = ', )
if ( == 0):
= val
= self
else:
temp = + 1
node = Tree(val)
=
if(temp % 2 == 0):#Added nodes are left children
= node
else:
= node
while(temp != 0):
if ( < ):# If the added node is larger than the value of its parent node
p = # First save its three chains
LeftTemp =
RightTemp =
if ( != p):# Determine that it is not a head node
if (int(temp / 2) % 2 == 0):# The father of the added node is the left child
= node
else:
= node
=
else:
= node#If it is a head node, then connect its father to itself.
=
self = node
if(temp % 2 == 0):#Added nodes are left children
= p
=
if ( != None):
= node
else:
=
= p
if ( != None):
= node
= LeftTemp
= RightTemp
= node
temp = int(temp / 2)
#print(' = ', , ' = ', )
#print('Tree = ')
#()
else:
break;
+= 1
return self
#Re-align the heap after taking out the head node
def Adjust(self):
#print('FrontSelfTree = ')
#()
#print('MSelfTree = ')
#()
print('Get ', )
p = ()
#print(' = ', )
#print(' = ', )
root = p
if ( % 2 == 0):
= None
else:
= None
#print(' = ', )
#print(' = ', )
= p# Move the last leaf node of a binary tree to the head node
=
=
while(1):#Optimization is the root of all evil
LeftTemp =
RightTemp =
FatherTemp =
if ( != None and !=None):# Determine the left posterior child of the node being processed at this time
if ( < ):
next =
else:
next =
if ( < ):
break;
elif ( == None and != None and > ):
next =
elif ( == None and != None and > ):
next =
else:
break;
=
=
= next
if ( != None):# After that it's a series of chains of swapped nodes that are processed
= p
if ( != None):
= p
if (FatherTemp == p):
= next
root = next
else:
== FatherTemp
if ( == p):
= next
else:
= next
if (next == LeftTemp):
= RightTemp
= p
if (RightTemp != None):
= next
else:
= LeftTemp
= p
if (LeftTemp != None):
= next
#print('Tree = ')
#()
= - 1
return root
if __name__ == '__main__':
print("My test results.")
root = Tree()
number = [-1, -1, 0, 0, 0, 12, 22, 3, 5, 4, 3, 1, 6, 9]
root = (number)
while( != 0):
root = ()
Run results:
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.