除了之前文章介绍的方法外，我们也可以通过sink的方式来排序，但是第一步都是相同的，保证堆有序
就是每次首位交换以后，把根目录上的元素下沉到应该在的位置，逻辑上比上一个方法要复杂一些：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#-*-coding:utf-8-*- def heap_sort(ary) : n = len(ary) print 'length of arr is :',n first = int(n/2-1) #最后一个非叶子节点 for start in range(first,-1,-1) : #构造大根堆 max_heapify(ary,start,n-1) print '第一次排序之后，应该是每个父节点都大于子节点',ary for end in range(n-1,0,-1): #堆排，将大根堆转换成有序数组 print 'end is :',end print 'exchange the first and last :' print 'before exchange:',ary print 'print [0]',ary[0] print 'print [end]',ary[end] ary[0],ary[end] = ary[end],ary[0] print 'after exchange ,and this is before sink:',ary sink(0,ary,end) print '#####:',ary return ary #最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点 #start为当前需要调整最大堆的位置，end为调整边界 def max_heapify(ary,start,end): root = start while True : child = root*2 +1 #调整节点的子节点 if child > end : break if child+1 <= end and ary[child] < ary[child+1] : child = child+1 #取较大的子节点 if ary[root] < ary[child] : #较大的子节点成为父节点 ary[root],ary[child] = ary[child],ary[root] #交换 root = child else : break def sink(k,arr,end): while 2 * k < end: if k == 0: temp = 1 else: temp = 2 * k + 1 if arr[temp] < arr[temp + 1] and temp+1<end: temp = temp + 1 else: pass if temp >= end: pass else: if arr[temp] > arr[k]: print '--------------sink-------' print arr arr[k],arr[temp] = arr[temp],arr[k] print arr print '--------------' else: print '--------------notsink-----' k = temp print 'temp:',temp return arr if __name__ == '__main__': array=[6,5,3,1,8,7,2,4] print heap_sort(array) |
Latest posts by Zhiming Zhang (see all)
- aws eks node 自动化扩展工具 Karpenter - 8月 10, 2022
- ReplicationController and ReplicaSet in Kubernetes - 12月 20, 2021
- public key fingerprint - 5月 27, 2021