算法连载之堆排序

发布于:2019-05-26   编辑:admin 浏览:

  堆是一个数组,可以看作是一个近似的完全二叉树,每一个节点对应一个相应数组的元素。例如数组:[0, 7, 0, 4, 8, 2, 2, 5, 1, 6]。如下就是一个堆:

  1、假设位置i的节点,左子节点是i*2,右子节点是i*2+1,父节点是i/2(向下取整,除根节点外)。

  3、n个元素的堆,叶节点分别是n/2+1(向下取整),n/2+2,......,n

  1、构建最大堆:首先将数组自底向下(n~1)构建一个最大堆。对于所有叶节点都是符合规则最朴实的最大堆,因此我们从n/2(向下取整)非叶节点开始逐个节点构建最大堆,以符合最大堆性质。

  2、维护最大堆:调整指定节点最大堆的过程,将指定节点同左节点元素比较,取最大值,然后再和右节点比较,取最大值,如果最大值节点同指定节点不同,则交换。原最大值节点交换后可能不符合最大堆,因此重复构建,直到完全满足最大堆结束。

  3、此时,最大堆的根节点就是数组的最大值,同第n个元素交换。此时堆的长度变为n-1;由于第一个元素被交换,因此第一个元素可能不符合最大堆性质。执行第2步调整第一个节点为最大堆。同理,此时根节点同第n-1个元素交换,此时堆的长度变为n-2。重复执行第3步直到堆只有一个元素结束。

  构建最大堆的时间复杂度是O(n),循环交换第一个元素接着维护最大堆时间复杂度是O(nlgn)。因此,舍弃低阶项,堆排序的时间复杂度是O(nlgn)。

  \u5806\u662f\u4e00\u4e2a\u6570\u7ec4\uff0c\u53ef\u4ee5\u770b\u4f5c\u662f\u4e00\u4e2a\u8fd1\u4f3c\u7684\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u6bcf\u4e00\u4e2a\u8282\u70b9\u5bf9\u5e94\u4e00\u4e2a\u76f8\u5e94\u6570\u7ec4\u7684\u5143\u7d20\u3002\u4f8b\u5982\u6570\u7ec4\uff1a[0,\u00a07,\u00a00,\u00a04,\u00a08,\u00a02,\u00a02,\u00a05,\u00a01,\u00a06]\u3002\u5982\u4e0b\u5c31\u662f\u4e00\u4e2a\u5806\uff1a

  \u6700\u5927\u5806\uff1a\u6240\u6709\u8282\u70b9\u5c0f\u4e8e\u7b49\u4e8e\u7236\u8282\u70b9\u3002

  \u6700\u5c0f\u5806\uff1a\u6240\u6709\u8282\u70b9\u5927\u4e8e\u7b49\u4e8e\u7236\u8282\u70b9\u3002

  点击“提交”后,我们会向您的邮箱发送一封验证邮件,请按照邮件中的提示完成操作。