Full tree and minimum heap instances of Python data Structures and algorithms

An example of Python data structure and algorithm is presented in this paper. To share for your reference, specific as follows:

#  Complete the tree   The minimum heap 
class CompleteTree(list):
  def siftdown(self,i):
    """  right 1 The full tree is adjusted downward, passing in the node number that needs to be adjusted downward i
     When the smallest element is removed, when the new element is added 1 When the number is placed on top of the heap, 
     If this is not a minimum heap, you need to adjust this number downward until you find the right location """
    n = len(self)
    #  when  i  The node has a son (at least a left son), and when adjustments are needed, the loop executes 
    t = 0
    while i*2+1<n:
      # step 1 : Find the smallest son from the left son and the right son of the current node 1 And pass on their Numbers t
      if self[i] > self[i*2+1]:
        t = i*2+1
      else: t = i
      #  If there is a right son, discuss the right son again 
      if i*2+2<n:
        if self[t] > self[i*2+2]: t = i*2+2
      # step 2 : The element and node in the smallest node i Element exchange of 
      if t != i:
        self[t],self[i] = self[i],self[t]
        i = t  #  update i For the number of the son node with which it has just been swapped so that it can be adjusted further down 
      else:
        break  #  This indicates that the current parent is smaller than the two children, ending the adjustment 
  def siftup(self,i):
    """  right 1 A full tree is adjusted upwards, passed in 1 Number of nodes that need to be adjusted upwards i
       When you want to add 1 After a new element, on the bottom of the heap (finally 1 The) elements are adjusted  """
    if i==0: return
    n = len(self)
    if i < 0: i += n
    #  Note that because of the nature of the heap, there is no need to consider the left son 
    #  Because the parent is definitely smaller than the child, you just have to compare 1 time 
    while i!=0:
      if self[i]<self[(i-1)/2]:
        self[i],self[(i-1)/2] = self[(i-1)/2],self[i]
      else:
        break
      i = (i-1)/2   #  update i Number its parent, so it's easy to do 1 The next upward adjustment continues 
  def shufflePile(self):
    """  In the current state, adjust the tree to make it 1 A pile of  """
    #  from " The bottom of the pile " to " Pile top " Make downward adjustments so that the smallest elements keep rising 
    #  This will enable i The heap below the node is the local minimum heap 
    for i in range((len(self)-2)/2,-1,-1):  # n/2,...,0
      self.siftdown(i)
  def deleteMin(self):
    """  Delete the smallest element  """
    t = self[0]   #  with 1 A temporary variable that records the top of the heap 
    self[0] = self[-1] #  Will stack at the end 1 Assign a value to the top of the heap 
    self.pop()   #  Delete the last 1 An element 
    self.siftdown(0)  #  Downward adjustments 
    return t
  def heapsort(self):
    """  Heap sort operations on elements in the heap  """
    n = len(self)
    s = []
    while n>0:
      s.append(self.deleteMin())
      n -= 1
    #  Since all the elements in the heap have popped out, splice the sorted elements into the original heap 
    self.extend(s)
if __name__=="__main__":
  a = [99,5,36,7,22,17,92,12,2,19,25,28,1,46]
  ct = CompleteTree(a)
  print ct
>>> [99, 5, 36, 7, 22, 17, 92, 12, 2, 19, 25, 28, 1, 46]
  ct.shufflePile()
  print ct
>>> [1, 2, 17, 5, 19, 28, 46, 12, 7, 22, 25, 99, 36, 92]
  s = ct.heapsort()
  print ct
>>> [1, 2, 5, 7, 12, 17, 19, 22, 25, 28, 36, 46, 92, 99]

For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Encryption and Decryption Algorithm and Skills Summary, Python Coding skills Summary, Python Function Use Skills Summary, Python String Manipulation Skills Summary and Python Introduction and Advanced Classic Tutorial.

I hope this article has been helpful in Python programming.