什么是堆？     堆是以完全二叉树形式存储的一组数据。 堆排序步骤 1、建立堆     用层次遍历的方式将一组数值构建成一棵树。 2、调整堆      刚建立的树是未完成排序的，需要对构建好的树进行调整。这里需要先了解2个概念：      大顶堆，小顶堆。      什么是大顶堆、小顶堆呢？如果我们用层次遍历的方式从数值1开始依次对第一步建成的树的顶点给一个标号的话，那么大顶堆需要满足以下条件：1号顶点的值>=2号顶点的值>=3号顶点的值，如果顶点的标号用变量i表示的话可推导出以下公式：i>=2i>=2i+1。小顶堆则刚好相反，可表示为i<=2i<=2i+1。     虽然明白了上面的定义，但是现在还是不能下手对第一步构建的树进行调整。因为上面的定义只告诉了我们排序完成后的堆是什么样子的，还差了一把让我们动手的钥匙。     现在让我们来分析一下这把钥匙是什么？一个完全二叉树有以下特性：顶点总数/2+1的顶点是叶子节点，而且由于树的存储结构是单向的，叶子节点没有指向父节点的指针。所以要比较节点值大小的话一定要从一个父节点开始。如果一棵树的节点数为n的话，那我们就应该从n/2号顶点开始比较。但是假如n是一个奇数呢？那我们就直接取整。至于原因大家画一个5或9个节点的树分析一下就知道了。    好了正式动手，按大顶堆排序调整这棵树吧。方法如下：     1、假如有该父节点只有一个孩子节点，且父节点值>孩子节点。不用调整     2、假如有该父节点只有一个孩子节点，且父节点值<孩子节点。值互换     3、假如有该父节点有两个孩子节点，且父节点值>2个孩子节点。不用调整      4、假如有该父节点有两个孩子节点，且父节点值<2个孩子节点。和最大值的孩子节点互换      5、假如有该父节点有两个孩子节点，且父节点值<1个孩子节点。同2      调整后继续n/2-1号节点的调整，直到完成根节点的调整。      调整后的子树不符合大顶堆的定义则重复上面1-5步骤。 3、读出序列      用层次遍历的方式读出序列。  

评论