目录

一、基本概念

二、大小堆

三、堆实现heapify

1、把列表转化为堆 【大项堆】

 2、对堆做 heapify

2.1  树的第四层子节点，和父节点，第三层层进行大项堆比较，【红色的是比较交换后的数字】​编辑        

2.2  树的第三层子节点，和父节点，第二层进行大项堆比较，【绿色的是比较交换后的数字】 

​2.3 树的第二层子节点，和父节点，第一层进行大项堆比较，【换色色的是比较交换后的数字】 ​编辑

2.4 代码来实现

 3、对堆进行排序

3.1 最后的节点和根节点做交换【5，50做交换】，砍掉最后的节点

3.3 、在对节点做heapify，之后，根节点在和最后的最后的节点，做交换【48，5】，砍掉最后的节点

 3.3 、以此类推，根节点在和最后的最后的节点，做交换【47，5】，砍掉最后的节点，其他的节点也是这样实现，就不一一列举了

3.4 代码实现这部分排序

 四、完整代码

一、基本概念

首要需要理解的堆是由树组成，一种叫做完全二叉树的数据结构。

二、大小堆

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
可以得到的排序排序的列表
 

对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

三、堆实现heapify

1、把列表转化为堆 【大项堆】

listF = [4, 48, 3, 50, 4, 47, 5, 38, 15, 46, 19, 44, 27, 26, 36]

parent_node = (i -1) /2   # i 代表再树中索引的位置  
lef_node = 2 * i +1  
ritht_node = 2 * 1 +2

 2、对堆做 heapify

        2.1  树的第四层子节点，和父节点，第三层层进行大项堆比较，【红色的是比较交换后的数字】
        2.2  树的第三层子节点，和父节点，第二层进行大项堆比较，【绿色的是比较交换后的数字】 

 2.3 树的第二层子节点，和父节点，第一层进行大项堆比较，【换色色的是比较交换后的数字】 

  2.4 代码来实现

• 1、对第四层、第三层、第二层、第一层，进行递归调用heapify 方法大项堆的排序
• 2、实现大项堆比较排序

# 1、建立大顶堆
def buildMaxHeap(arr,n):
    # arr 代表当前排序的列表，n 表示当前树的数据范围【及arr的个数】
    last_node_index = n -1  #最后的的节点的索引
    parent_node_index = int((last_node_index-1)/2)
    if parent_node_index >= 0:
        for i in range(parent_node_index,-1,-1):
            #i 是这个堆现在有多少个节点
                heapify(arr=arr,i=i,n=n)
 
#2、子节点和父节点进行最大值交换
def heapify(arr,i,n):
    #arr 代表当前排序的列表， i 当表当前的书的parent node ,n 表示当前树的数据范围【及arr的个数】
    left = 2 * i + 1 #找出左节点的索引
    right = 2 * i + 2 #书中右节点的索引
    largest = i  #当前的parent
 
    #如果有左节点，并且左节点的值更大，更新最大值的索引 left < n越界
    if left < n and arr[left] > arr[largest]:   # 判断是否，（left < n）越界
        largest =left
    # 如果有右节点，并且右节点的值更大，更新最大值的索引
    if right < n and arr[right] > arr[largest]: #判断是否，（left < n）越界
        largest = right
 
    #如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换
    if largest != i:
        arr[i] ,arr[largest] =arr[largest],arr[i]  #节点值进行互换
        heapify(arr,largest,n)

 3、对堆进行排序

3.1 最后的节点和根节点做交换【5，50做交换】，砍掉最后的节点

 

 

3.3 、在对节点做heapify，之后，根节点在和最后的最后的节点，做交换【48，5】，砍掉最后的节点

 3.3 、以此类推，根节点在和最后的最后的节点，做交换【47，5】，砍掉最后的节点，其他的节点也是这样实现，就不一一列举了

3.4 代码实现这部分排序

 

def heapSort(arr):
    if arr == None or len(arr) ==0:
        return
    n = len(arr)
    #构建大顶堆，变成一个大顶堆的数组
    buildMaxHeap(arr,n)
    if n >0:
        for a in range(n-1,0,-1):
            arr[a], arr[0] = arr[0], arr[a]
            heapify(arr,0,a)
    return arr

 四、完整代码

listF = [4, 48, 3, 50, 4, 47, 5, 38, 15, 46, 19, 44, 27, 26, 36]
# 1、建立大顶堆
def buildMaxHeap(arr,n):
    # arr 代表当前排序的列表，n 表示当前树的数据范围【及arr的个数】
    last_node_index = n -1  #最后的的节点的索引
    parent_node_index = int((last_node_index-1)/2)
    if parent_node_index >= 0:
        for i in range(parent_node_index,-1,-1):
            #i 是这个堆现在有多少个节点
                heapify(arr=arr,i=i,n=n)
 
def heapify(arr,i,n):
    #arr 代表当前排序的列表， i 当表当前的书的parent node ,n 表示当前树的数据范围【及arr的个数】
    left = 2 * i + 1 #找出左节点的索引
    right = 2 * i + 2 #书中右节点的索引
    largest = i  #当前的parent
 
    #如果有左节点，并且左节点的值更大，更新最大值的索引 left < n越界
    if left < n and arr[left] > arr[largest]:   # 判断是否，（left < n）越界
        largest =left
    # 如果有右节点，并且右节点的值更大，更新最大值的索引
    if right < n and arr[right] > arr[largest]: #判断是否，（left < n）越界
        largest = right
 
    #如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换
    if largest != i:
        arr[i] ,arr[largest] =arr[largest],arr[i]  #节点值进行互换
        heapify(arr,largest,n)
 
def heapSort(arr):
    if arr == None or len(arr) ==0:
        return
    n = len(arr)
    #构建大顶堆，变成一个大顶堆的数组
    buildMaxHeap(arr,n)
    if n >0:
        for a in range(n-1,0,-1): #从 n -1 最后一个节点出发
            arr[a], arr[0] = arr[0], arr[a]
            heapify(arr,0,a)
    return arr
 
print(heapSort(listF))