堆排序

二叉树

堆排序需要先了解二叉树的基本常识,注意区分完全二叉树和非完全二叉树,以及要了解二叉树在计算机中的存储方式。

这是一棵完全二叉树

堆排序

它在计算机中的存储方式为:

堆排序

如上图所示,完全二叉树在计算机中存储时就像一个链表,只不过要怎么对应父节点和子节点的关系呢?根据这个二叉树看这个链表,分析列表下标中,父节点与子节点的关系,得出结论:

父节点与左子节点的关系为,父节点的下标乘以2加上1,公式:i -> 2i+1

父节点与右子节点的关系为,父节点的下标乘以2加上2,公式:i -> 2i+2

子节点与父节点的关系为,子节点下标减1整除2,公式:(n-1)//2 -> i

 

二叉树与堆的关系

堆是特殊的二叉树结构,分为大根堆、小根堆

大根堆定义:完全二叉树中,任意一个节点都比其子节点大。如图:

堆排序

小根堆定义:完全二叉树中,任意一个节点都比其子节点小。如图:

堆排序

堆的向下调整性质

如果节点的左右都是堆,但自身不是堆时,可以向下调整,如图:

堆排序

根节点2左右都是大根堆,但是自身不是大根堆,就选取两个子节点中最大值的子节点进行对换,2与9对换之后发现自身同样还不是堆,继续向下调整,挑选最大值的子节点对换,2与8对换,发现还不是堆,继续与6对换,然后终于形成堆了,如图:

堆排序

所以,堆排序中堆拥有一个向下调整的性质:假设根节点左右都是堆,但自身不满足堆的时候,可以通过一次向下调整来将其调整成为一个堆。

堆排序过程

1、建立堆

输入一段无序的数,通过先让最底层节点有序,先调整底层,再调整整体,比如:

堆排序

将3和5对换,变成:

堆排序

依次调整,只不过9的节点是有序的,所以不用调整:

堆排序

但是1的节点是无序的,所以需要调整:

堆排序堆排序

堆排序堆排序

堆排序堆排序

最后得到个大根堆。

2、得到堆顶元素

我们得到一个有序堆,堆顶的元素为9,是这个堆中最大的数。

堆排序

3、去掉堆顶,将堆最后一个元素放到堆顶,通过向下调整使堆有序,堆顶就是第二大元素

我们取走堆顶元素,将堆底部最后一个元素放到堆顶:

堆排序堆排序

根据堆的性质向下调整得到:

堆排序

再取走堆顶元素,再次把3调整到堆顶:

堆排序

向下调整:

堆排序

取走堆顶7,将堆尾2放到堆顶向下调整:

堆排序堆排序

4、重复3步骤,直到堆为空

代码实现

def sift(li, low, high):
    """
    向下调整函数

    :param li: 列表
    :param low: 堆根节点
    :param high: 堆尾节点
    :return:
    """
    i = low     # 父节点
    j = 2 * i + 1   # 左子节点
    tmp = li[low]   # 存储堆顶
    while j <= high:    # j的位置有效,就一直循环
        if j+1 < high and li[j+1] > li[j]: # 如果右子节点比左子节点大且右子节点下标不大于根尾下标
            j += 1  # 则指针指向右子节点
        if li[j] > tmp: # 如果子节点大于tmp
            li[i] = li[j]   # 将子节点更换到父节点去
            i = j   # 父指针切换到子节点上
            j = 2*i+1   # 子指针切换到下一个左子节点上
        else:   # 否则就是tmp大
            break
    li[i] = tmp     # tmp就放在该父节点上(跳出循环时,tmp的值还没放进堆里面)

def heap_sort(li):
    """

    :param li:
    :return:
    """
    n = len(li)
    for i in range((n-2)//2, -1, -1):   # 构造堆函数,i代表构造堆的时候部分的根下标
        sift(li, i, n-1)
    for i in range(n-1, -1, -1):    # i是指向堆的最后一个元素
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i-1)

li = [x for x in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)

 

上一篇:【题解】【老C的任务】


下一篇:剑指 Offer II 047. 二叉树剪枝