《数据结构-用C语言描述》第八章 堆

第8章堆21世纪高等院校规划教材返回总目录1©

2006堆2©

2006了解堆与其的插入和删除操作关于min-heap关于min-max

heap

及其插入和删除操作关于Deap及其插入和删除操作什么是堆3©

2006堆（Heap）和二叉查找树大致相同。堆的定义如下：堆是一棵二叉树，其树根的键值大于子树的键值，而且必须是完全二叉树。不管左子树和右子树的大小顺序，这是堆与二叉查找树最大的差异。大致可分为：Max-heap、Min-Max

heap及Deap堆具有新增、删除、输出数据3个功能堆（Heap）的插入4©

2006例：在一棵Heap中插入30及50 步骤如下：按照完全二叉树的特性将30插进来，如图8-9所示。插入50，但是此时已经不是一棵Heap，要进行调换。进行调换后，将要插入的那一个节点往上调整即可，如图8-10所示。堆（Heap）的插入—示意图Heap示图5©

2006图8-9插入30后的完全二叉树状态图图8-10插入50后的完全二叉树状态图堆（Heap）的删除Heap的删除：-Heap的删除则将完全二叉树的最后一节点取代被删除的节点，然后判断是否为一棵Heap，若不是，则再依照上述方法进行调整。删除30后的调整方法如图8-11所示。图8-116©

2006删除30后的调整方法什么是min-Heap堆除了max-heap外，还可细分为min-heap、min-max-heap、deap等。min-heap的概念十分简单，其节点键值一律小于小节点，恰与max-heap相反，如图8-22所示即为min-heap的一个例子。图8-227©

2006min-heap示意图min-max

heap的定义min-max-heap包含了min-heap与max-heap两种堆的特征，如图8-27所示即为一棵min-max-heap：8©

2006min-max

heap的定义9©

2006min-max-heap必须符合下列3项定义：■■■—min-max-heap是以一层min-heap、一层max-heap 交互构成的—树中为min-heap的部分，仍需符合min-heap的特 性—树中为max-heap的部分，仍需符合max-heap的特 性min-max

heap的插入10©

2006虽然max-max-heap的插入与max-heap的原理差不多，但是插入后，要调整至符合min-max-heap的定义。例：假设已存在一棵min-max-heap，如图8-28所示。■■向其插入5的操作步骤如下：（1）插入5，如图8-29所示；（2）进行调整：插入5后18>5,不符合定义第一项；（3）再次进行调整：当步骤（2）调整后10>，不符合定义第二 项；（4）操作结束，符合min-max-heap的定义。min-max

heap的插入图8-28min-max-heap示意图图8-29插入5后的示意图图8-30插入5■5■与■18■交■换5与10交换图8-31交换5和10后的示意图11交换5和18后的示意图©

2006min-max

heap的删除12©

2006min-max-heap的删除同min-max-heap的插入一样，其结果要符合定义。若删除min-max-heap的最后一个节点，则直接删除即可；否则，先将删除节点键值与树中的最后一个节点对调，再做调整操作，即以最后一个节点取代被删除节点。DeapDeap同样也具备max-heap与min-heap的特征。图8-41

Deep示意图13©

2006Deap其定义如下：（1）Deap的树根不储存任何数据，为一空节点。（2）树根的左子树，为一棵min-heap；右子树则为max-heap。（3）min-heap与max-heap存在对应关系。Deap的插入和删除14©

2006Deap的插入操作与