堆排序算法

堆排序算法是一个基于完全二叉树形结构的排序算法。二叉树是需要抽象出来的,只是为了方便来理解排序的过程。

堆排序算法有大根堆和小根堆, 这里我们以大根堆为例。对于堆排序来说,存在这样的特性根节点大于等于他的孩子节点。

对于一个数组来说,怎么看成是一颗二叉树呢。数组是把二叉树每一层遍历后存储的一种形式。

1.抽象出二叉树

对于数组6, 7, 4, 3,8的树形结构可以表示如下。对于任何一个元素的下标i, 左孩子是2*(i+1)-1 下标所在的位置, 右孩子是 2*(i+1)所在的位置。

数组的二叉树形式

2.建立大根堆

建立的堆就是这样的形式,根节点大于左右孩子。很显然数组第一个算法是最大值所在的位置。

大根堆

3.排序提取堆顶元素

排序过程,把对最大元素8与数组的最后一个元素调换位置,这个时候8就来到了数组的最后位置,6就来到了数组的第一个元素。

8放到最后位置,并且固定

最后那个位置需要固定住,是我们找到的第一个最大元素。

4.重新调整堆

这个时候发现堆的条件不成立了,重新调整堆的结构。

重新调整后的堆的结构

5.再次提取堆顶元素,重复3-4的过程

看一下python实现的堆排序代码:

def heap_adjust(elements, i, n):
    l = 2 * (i + 1) - 1
    r = 2 * (i + 1)
    k = i
    if r >= n or l >= n:
        return

    if elements[l] < elements[r]:
        k = r
    elif elements[l] > elements[r]:
        k = l

    if elements[i] < elements[k]:
        elements[i], elements[k] = elements[k], elements[i]
        heap_adjust(elements, k, n)


def heap_sort(elements):
    n = len(elements)
    for i in range(int(n / 2), -1, -1):
        heap_adjust(elements, i, n)

    for i in range(n - 1, -1, -1):
        elements[i], elements[0] = elements[0], elements[i]
        heap_adjust(elements, 0, i)


if __name__ == '__main__':
    arr = [6, 7, 4, 3, 8]
    heap_sort(arr)
    print(arr)

运行结果:

[3, 4, 6, 7, 8]

更多内容请关注公众号:IT技术漫漫谈

版权声明:
作者:一点一线
链接:https://jkboy.com/archives/18223.html
来源:随风的博客
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
打赏
海报
堆排序算法
堆排序算法是一个基于完全二叉树形结构的排序算法。二叉树是需要抽象出来的,只是为了方便来理解排序的过程。
<<上一篇
下一篇>>