堆结构

 1 class Solution:
 2     def maxheap(self,arr):
 3         length = len(arr)
 4         for i in range(len(arr)//2,-1,-1): #之所以从len(arr)//2开始是因为 len(arr)//2为最后一个非叶节点
 5             self.heaprify(arr,i,length)
 6 
 7     def heaprify(self,arr,i,length):
 8         left = 2*i+1
 9         right = 2*i+2
10         largest = i
11         if left<length and arr[left]>arr[largest]:
12             largest = left
13         if right<length and arr[right]>arr[largest]:
14             largest = right
15         if largest!=i:
16             arr[largest],arr[i] = arr[i],arr[largest]
17             self.heaprify(arr,largest,length)
18 
19     def heapSort(self,arr):
20         self.maxheap(arr)
21         length = len(arr)
22         for i in range(len(arr)-1,-1,-1):
23             arr[0],arr[i] = arr[i],arr[0]
24             length-=1
25             self.heaprify(arr,0,length)
26         return arr