【数据结构算法】：Python实现堆排序

超、凢脫俗 2022-05-16 02:16 178阅读 0赞

### 动图展示 ###

算法时间复杂度  
![849589-20171015231308699-356134237.gif][]

### python ###

堆：程序运行过程中动态分配的内存，比如c中的malloc和c++中的new。这种效率会比较慢，但不用预先定义。  
栈：操作系统在建立某个进程或线程时，为其创建的内存空间，该内存空间具有FIFO的特性。当程序结束时，只需要修改栈的头指针就可以直接释放内存了，因此这种效率较快，但需要预先定义。  
堆排序的思想：堆是一种数据结构，在这里我们可以将这个堆看成是一种特殊的完全二叉树，该二叉树的特点是其非叶子节点的数必定要大于（或者）小于其子节点上的数。[完全二叉树概念][Link 1]  
堆排序就是一个构建最大堆或最小堆的过程（本例子只讲建立最大堆），每次构建一个最大堆后，将该最大堆的根节点和最右边的叶子节点进行交换，并脱离堆。然后对剩下的len-1个节点的堆再进行构建最大堆的过程，直到所有的节点都脱离堆之后排序完成。

在模仿堆的数据结构的时候（完全二叉树），对于节点的编码利用最直观的层序遍历。可以利用一维数组实现，这种情况下对于起始索引为0的一维数组来说：  
**父节点i**的左孩子索引为**2i+1**；  
右孩子索引为**2i+1+1**；  
**子节点i**对应的父节点索引为**floor( (i-1)/2 )**，表示向下取整。

def build_max_head(arr,heapsize,root_index):
        #根据给定的根节点计算左右节点的index
        left_index = 2*root_index+1
        right_index = left_index+1
        max_num_index = root_index
        #如果左节点大于根节点，那么max_num_index=left_index
        if left_index<heapsize and arr[left_index]>arr[max_num_index]:
        max_num_index=left_index
        #如果右节点大于根节点，那么max_num_index=right_index
        if right_index<heapsize and arr[right_index]>arr[max_num_index]:
        max_num_index=right_index
        if  max_num_index != root_index:
            arr[root_index],arr[max_num_index] = arr[max_num_index],arr[root_index]
            #进行下一个节点的build_max
            build_max_head(arr,heapsize,max_num_index)
    
    def head_sort(arr):
        #从最后一个节点开始，对整个堆（完全二叉树）进行build_max
        for i in range((len(arr-1)-1)/2,-1,-1):
            build_max_head(arr,len(arr),i)
        #对从最后一个节点开始往前遍历
        for i in range(len(arr)-1, -1, -1):
            #这个时候最大值就在根节点
            #所以把这个最大值放到有序队列中
            #简单来说就是把最大值放到最后
            arr[i],arr[0] = arr[0],arr[i]
            #互换之后，堆中就少了一个元素，所以当前堆的个数变了，变为i
            #此时由于堆只变了根节点，因此只需要对根节点进行build_max
            build_max_head(arr,i,0)
    if __name__ == '__main__':
        arr = [1,3,5,7,9,2,8,0,-1,-2]
        output = merge_sort(arr)
        print output

[849589-20171015231308699-356134237.gif]: /images/20220516/4ab4714cfc344a8797341750cefd9b14.png
[Link 1]: https://blog.csdn.net/qiu931110/article/details/80887393