数据结构-基于C++语言（微课版） 课件 1-2-2 堆排序

堆排序概念；堆的调整；本节目录：本节内容：堆排序堆排序概念堆排序是另一种基于选择的排序方法，是指利用堆这种数据结构所设计的一种排序算法，可以有效提高排序的效率。堆排序2348376086705098堆堆的构造目的：查找到堆中最大的关键字;堆的调整堆排序例295315277638

123456关键字：

目的：依次查找到其它较大的关键字,从而实现排序。765338272915堆堆的调整堆排序例295315277638

123456关键字：

1）首先，将堆顶元素与堆中最后一个元素交换位置，其不再参与堆的排序，该元素已经有序。在图中用虚线表示。765338272915堆堆的调整堆排序例295315277638

123456关键字：

382729537615155338272976堆

1）首先，将堆顶元素与堆中最后一个元素交换位置，其不再参与堆的排序，该元素已经有序。在图中用虚线表示。堆的调整堆排序例295315277638

123456关键字：

382729537615382729537615155338272976堆

1）首先，将堆顶元素与堆中最后一个元素交换位置，其不再参与堆的排序，该元素已经有序。在图中用虚线表示。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:首先调整第3个关键字：i=5/2=3；然后是第2、第1个关键字。382729537615155338272976堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。382729537615155338272976堆例295315277638

123456关键字：

PS:调整关键字序号i=5/2=3、2、1调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。382729537615155338272976堆例295315277638

123456关键字：

PS:调整关键字序号i=5/2=3、2、1调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=5/2=3、2、1382729537615155338272976堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=5/2=3、2、1382729537615155338272976堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=5/2=3、2、1382729537615155338272976堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=5/2=3、2、1382729537615531538272976堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=5/2=3、2、1382729537615532938271576堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=5/2=3、2、1382729537615532938271576堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

2）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=5/2=3、2、1382729537615382729537615152938275376堆调整过程编号为i的结点与2i、2i+1的结点比较，若结点i的值小于孩子结点的值，则结点i与其中较大者的结点交换，直到叶结点或不再交换为止；堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=4/2=2、1382729537615152938275376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=4/2=2、1382729537615152938275376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=4/2=2、1382729537615152938275376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=4/2=2、1382729537615382915275376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=4/2=2、1382729537615382915275376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=4/2=2、1382729537615272915385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=4/2=2、1382729537615272915385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=3/2=2、1382729537615272915385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=3/2=2、1382729537615272915385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=3/2=2、1382729537615292715385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=3/2=2、1382729537615292715385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=3/2=2、1382729537615152729385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=2/2=1382729537615152729385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=2/2=1382729537615271529385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=2/2=1382729537615271529385376堆调整过程父结点与左右孩子结点比较大小，确保父结点是最大的。堆的调整堆排序例295315277638

123456关键字：

3827295376152）从第i=⌈n/2⌉个关键字开始调整，调整完成后到下一步。3）令i=i-1，重复步骤2，直到i=1，堆的调整结束。PS:调整关键字序号i=2/2=1382729537615152729385376堆调整过程父结点与左右孩