堆排序

作者: Uzero | 来源:发表于2018-10-06 14:02 被阅读0次

    思路:

            1、把无序数组构建成最大二叉堆

            2、循环删除堆顶元素,移到集合尾部,调节堆产生新的堆顶

    当我们删除一个最大堆的堆顶(并不是完全删除,而是替换到最后面),经过自我调节,第二大的元素就会被交换上来,成为最大堆的新堆顶。

    正如上图所示,当我们删除值为10的堆顶节点,经过调节,值为9的新节点就会顶替上来;当我们删除值为9的堆顶节点,经过调节,值为8的新节点就会顶替上来.......

    由于二叉堆的这个特性,我们每一次删除旧堆顶,调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶,反复调节二叉堆,所得到的集合就成为了一个有序集合,

    code run

    相关文章

      网友评论

          本文标题:堆排序

          本文链接:https://www.haomeiwen.com/subject/orhhaftx.html