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

堆的概念；堆的特点；本节目录：本节内容：构造堆堆的构造堆构造的步骤；选择排序简单选择排序堆排序堆的定义堆是由n个元素组成的一个完全二叉树结构，并同时满足一定的条件。堆的构造就是n个元素{k1、k2、

k3…kn}，当且仅当各个元素之间的位置、以及大小满足如下关系。

从中可以看出，主要的考量的关系：父结点：ki左右孩子结点：k2i

，k2i+1

之间的大小关系。k1k2k3k4k5k6堆堆的定义堆是一个完全二叉树的结构，并同时满足一定的条件。堆的构造堆是由n个元素组成的序列{k1、k2、

k3…kn}，当且仅当各个元素之间的位置关系满足如下关系。

说明：1、根结点最大；2、每个结点为根的二叉树也是堆；k1k2k3k4k5k6堆堆的定义堆的构造765338272915按照关键字的序号，从上到下，从左到右排列成一个完全二叉树。满足：

ki

不小于k2i

、

k2i+1

。堆例295315277638

123456关键字：构造堆堆的构造在堆排序中，主要涉及两个问题。7653382729151、一是如何由一个无序序列建成一个堆？2、二是如何在输出堆顶记录之后，调整剩余记录，使之成为一个新的堆？例295315277638

123456关键字：堆构造堆堆的构造在堆排序中，主要涉及两个问题。例295315277638

1234567653382729151、一是如何由一个无序序列建成一个堆？2、二是如何在输出堆顶记录之后，调整剩余记录，使之成为一个新的堆？关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345629关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345629其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。53关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。29关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例29

5315277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。29关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例29

5315277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。2915关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例29

53

15277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。2915关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例29

53

15277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。291527关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例29

53

15

277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。291527关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。29152776关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345653其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。76152729关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345676其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。53152729关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345676其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。53152729构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345676其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。5315272938关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第一个结点是一个堆；例295315277638

12345676其次，当有新的结点要插入时，这个结点的位置首先与其对应位置上的父结点比较，如果比父结点大，则与父结点交换，一直向上交换，直到不大于父结点为止。5338272915关键字：构造堆堆的构造无序序列构造堆，可以通过构建一个二叉树的过程来实现。首先，确保第