如何详细创建PAT堆，实现A1098.InsertionorHeapSort(25)的堆排序过程？

本文共计1059个文字，预计阅读时间需要5分钟。

《篇首语：编程笔记》

篇首语：本文由编程笔记#自由互联小编为大家整理，主要介绍了PAT堆——A1098.InsertionorHeapSort(25)（内涵堆的详细创建过程）相关的知识，希望对你有一定的参考价值。

篇首语：本文由编程笔记#自由互联小编为大家整理，主要介绍了PAT 堆——A1098.Insertion or Heap Sort(25)（内涵堆的详细创建过程）相关的知识，希望对你有一定的参考价值。

堆的详细创建过程：参考：www.jianshu.com/p/21bef3fc3030明白堆的详细创建过程的前提是要理解Shift Down。但是这明显不符合最大堆的定义，所以我们需要让该完全二叉树转换成最大堆！怎么转换成一个最大堆呢？最大堆有一个特点就是其各个子树都是一个最大堆，那么我们就可以从把最小子树转换成一个最大堆，然后依次转换它的父节点对应的子树，直到最后的根节点所在的整个完全二叉树变成最大堆。那么从哪一个子树开始调整？

我们从该完全二叉树中的最后一个非叶子节点为根节点的子树进行调整，然后依次去找倒数第二个倒数第三个非叶子节点...

具体步骤

在做最大堆的创建具体步骤中，我们会用到最大堆删除操作中结点位置互换的原理，即关键字值较小的结点会做下沉操作。

• 1）、就如同上面所说找到二叉树中倒数第一个非叶子结点87，然后看以该非叶子结点为根结点的子树。查看该子树是否满足最大堆要求，很明显目前该子树满足最大堆，所以我们不需要移动结点。该子树最大移动次数为1。
• 2）、现在来到结点30，明显该子树不满足最大堆。在该结点的子结点较大的为72，所以结点72和结点30进行位置互换。该子树最大移动次数为1。