堆排序算法

一点一线 • 2023-01-02 • 云技术社区 • 413 阅读

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

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

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

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技术漫漫谈

本站文章资源均来源自网络，除非特别声明，否则均不代表站方观点，并仅供查阅，不作为任何参考依据！
如有侵权请及时跟我们联系，本站将及时删除！
如遇版权问题，请查看本站版权声明

THE END