软考题库
软件设计师 · 高频练习

最小堆插入新元素后，怎样沿父结点逐层上滤？

中级 单选题 第 916 题 中等 软件设计师最小堆完全二叉树上滤数据结构
内容整理：软考题库编辑部 最近更新：
题目

最小堆按层序存放为 [10,20,15,30,40,25]。插入元素 12 后，按最小堆规则上滤，最终层序序列是（）。

A [10,20,15,30,40,25,12]
B [10,12,15,30,40,25,20]
C [10,20,12,30,40,25,15]
D [12,10,15,20,40,25,30]
题目类型：原创高频练习题 用途：用于帮助理解软件设计师相关考点和答案解析，不等同于官方真题。
正确答案
C
答案解析

12 先放在完全二叉树末尾，即数组第 7 个位置，其父结点是第 3 个位置的 15。因为 12<15，二者交换；12 的新父结点为根 10，12>10，停止上滤，得到 [10,20,12,30,40,25,15]。

选项分析

A

错误。12 比父结点 15 小，不能原地不动。

B

错误。12 的初始父结点是 15，不是 20；堆调整沿实际父链进行。

C

正确。12 与 15 交换一次，在 10 下方停止。

D

错误。最小堆根必须是当前最小值 10，12 不应上滤到根之上。

本题为什么容易错

数组看起来像序列，很容易按相邻位置比较。堆数组的比较对象由树的父子下标决定，不是左邻和右邻。

先看结论

简短答案

最小堆插入新元素后，怎样沿父结点逐层上滤，正确答案是 C（[10,20,12,30,40,25,15]）。12 先放在完全二叉树末尾，即数组第 7 个位置，其父结点是第 3 个位置的 15。因为 12<15，二者交换；12 的新父结点为根 10，12>10，停止上滤，得到 [10,20,12,30,40,25,15]。

解析

易混淆概念对比表

概念本题判断区别要点记忆提示
[10,20,15,30,40,25,12] 本题干扰项 错误。12 比父结点 15 小，不能原地不动。 看到该词不要急着选，先判断是否真正解决题干问题
[10,12,15,30,40,25,20] 本题干扰项 错误。12 的初始父结点是 15，不是 20；堆调整沿实际父链进行。 看到该词不要急着选，先判断是否真正解决题干问题
[10,20,12,30,40,25,15] 本题正确答案 正确。12 与 15 交换一次，在 10 下方停止。 看到题干核心场景时优先联想到它
[12,10,15,20,40,25,30] 本题干扰项 错误。最小堆根必须是当前最小值 10，12 不应上滤到根之上。 看到该词不要急着选，先判断是否真正解决题干问题
本题易混淆选项怎么区分
  • [10,20,15,30,40,25,12]：错误。12 比父结点 15 小，不能原地不动。
  • [10,12,15,30,40,25,20]：错误。12 的初始父结点是 15，不是 20；堆调整沿实际父链进行。
  • [12,10,15,20,40,25,30]：错误。最小堆根必须是当前最小值 10，12 不应上滤到根之上。
复习

知识点详解

堆只保证父结点与子结点之间的偏序，不保证同层或整个数组有序。插入最多沿树高比较一次，时间复杂度为 O(log n)。使用 0 起始数组时父结点下标为 floor((i-1)/2)，使用 1 起始数组时为 floor(i/2)。建堆可从最后一个非叶结点向前下滤，复杂度通常为 O(n)。

备考速记

新元素先坐末位，只和父辈一路比。

数据结构在数据结构场景中的作用

数据结构在本题中的核心价值，是解决“最小堆按层序存放为 [10,20,15,30,40,25]。插入元素 12 后，按最小堆规则上滤，最终层序序列是（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。

拓展

同类题怎么考

  • 给定堆的层序数组，求插入后的结果。
  • 删除堆顶后将末元素移到根，再判断下滤路径。
数据结构在软件设计师软考中的考法

软考选择题通常不会只考概念定义，还会把数据结构放到数据结构场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。

解题思路

先找位置，再谈大小。原堆有 6 个元素，12 只能放到第 7 个位置，父结点是下标 3 的 15。交换一次后，12 来到下标 3；它再和根 10 比，已经不小于父结点，所以停。20、30、40 那一支没有参与比较，千万别顺手把数组排成全局升序。

考点定位

堆插入先保持完全二叉树形状，把新元素放到末尾；随后只沿祖先链调整，不需要重新排序整棵树。

易错提醒

  • 把最小堆误当成整个数组必须升序。
  • 1 起始下标时忘记父结点为 floor(i/2)。
  • 插入后同时调整无关子树，增加错误步骤。

备考提示

  • 先把数组下标写在元素上方，父子关系会清楚很多。
  • 删除堆顶用下滤，插入堆尾用上滤，两种方向分开记。

你可能还想了解

  • 最小堆为什么不是全局有序？
  • 堆插入和删除的调整方向有什么区别？
  • 0下标和1下标的堆父结点公式怎么写？

本文小结

12先追加到第7个位置，与父结点15交换后到第3位；再与根10比较时无需交换，所以最终为[10,20,12,30,40,25,15]。堆只沿父链上滤，不做全局排序。