我有一个大小为 10 的整数数组。我需要绘制完整的二叉树。现在我需要使用 siftup 过程插入其他三个元素。显示每次插入后的最大堆。
我不确定每次插入后显示的最大堆是什么。这是否意味着每次插入一个元素时我都需要显示最大堆的大小？
定义（最大堆） HEAP(X) 令 X 是一个完全有序的集合。X 上的堆要么是空的，∅，要么是一棵完全二叉树，t，包含 nt ≥ 1 个节点，每个节点都分配有 X 的值，这样：节点 i 的值 ≤ 节点 i 的父节点的值, 我 = 2,3,...,nt。堆的大小是树中节点的数量。当且仅当它的大小为 0 时，堆是空的。
最大堆的定义是这样的，但对我来说似乎有点模棱两可。
您需要在每次插入后显示生成的树。我的意思是，如果最初你有一个堆
3
/ \
1 2
然后插入一个 5，它将从最后一个堆位置开始，并会冒泡到堆头：
3 5
/ \ / \
1 2 => 3 2
/ /
5 1
类似地，如果你插入一个 4，那么：
5 5
/ \ / \
3 2 => 4 2
/ \ / \
1 4 1 3
简而言之，最大堆是父项的值大于其任何子项的值的堆。当您绘制初始完整二叉树时，它是否已经采用最大堆的形式？筛选（在我的大学里，我们称它为起泡，但除此之外）在这样的线程上解释起来有点复杂，所以我同意@DanteisnotaGeek。维基百科文章很好地说明了筛选过程的工作原理。插入后显示最大堆要求您绘制二叉树，以便在每次插入后满足最大堆属性。所以最后，你应该有你的初始树，一棵树有你的第一个插入，第二个插入和第三个插入，所以总共有 4 棵树。
在堆中，在任何时刻，从根节点到叶节点都是有序且线性的：
当您将元素插入堆中的下一个插槽时，该行的顺序将被更改：
所以，插入的最后一步变成了对线性数据结构进行重新排序：冒泡排序