python 排序（二）堆排序

我不是女神ヾ 2023-08-17 15:30 104阅读 0赞

## **一、简介** ##

**堆**：堆栈是计算机的两种最基本的数据结构，堆的特点是先进先出，栈是后进先出。堆其实可以理解成树的结构。堆在接受数据时先接收的数据会被先弹出。栈处于一级缓存而堆处于二级缓存中。

堆是一颗顺序存储的完全二叉树，有大根堆和小根堆。

大根堆：每个结点的key不小于其孩子结点的key，反之则是小根堆

**堆排序的思想：**本质是使用大根堆或小根堆来对一个数组进行排序

**操作步骤：**

以由对数组从小到大进行排序的情况，需要构建大根堆。

1.首先将整个数组进行构建一个大根堆得到\[0,R1,....,Rn\]（具体实现后面讲）

2.由于R1是最大的数，所以把R1与Rn改变位置，变成\[0,Rn,...,Rn-1,R1\]，此时\[0,Rn...,Rn-1\]是无序的，\[R1\]是有序的

3.对数组\[0,Rn...,Rn-1\]进行重构大根堆，得到\[0,R2,....,Rn-1\]

4.由于R2是最大的数，所以把R2与Rn-1改变位置，变成\[0,Rn-1,...Rn-2,R2,R1\]，此时\[0,Rn-1...,Rn-2\]是无序的，\[R2,R1\]是有序的

5.重复以上步骤，直到无序列表只有\[0\]，最终得到的有序序列则是按照从小到大规律排列的。

## **二、代码实现** ##

def heapify(arr, n, i): 
        largest = i  
        l = 2 * i + 1     # left = 2*i + 1 
        r = 2 * i + 2     # right = 2*i + 2 
      
        if l < n and arr[i] < arr[l]: 
            largest = l 
      
        if r < n and arr[largest] < arr[r]: 
            largest = r 
      
        if largest != i: 
            arr[i],arr[largest] = arr[largest],arr[i]  # 交换
      
            heapify(arr, n, largest) 
      
    def heapSort(arr): 
        n = len(arr) 
      
        # Build a maxheap. 
        for i in range(n, -1, -1): 
            heapify(arr, n, i) 
      
        # 一个个交换元素
        for i in range(n-1, 0, -1): 
            arr[i], arr[0] = arr[0], arr[i]   # 交换
            heapify(arr, i, 0) 
      
    arr = [ 12, 11, 13, 5, 6, 7] 
    heapSort(arr) 
    n = len(arr) 
    print ("排序后") 
    for i in range(n): 
        print ("%d" %arr[i]),