3

我有一个大小为 10 的整数数组。我需要绘制完整的二叉树。现在我需要使用 siftup 过程插入其他三个元素。显示每次插入后的最大堆。

我不确定每次插入后显示的最大堆是什么。这是否意味着每次插入一个元素时我都需要显示最大堆的大小？

定义（最大堆） HEAP(X) 令 X 是一个完全有序的集合。X 上的堆要么是空的，∅，要么是一棵完全二叉树，t，包含 nt ≥ 1 个节点，每个节点都分配有 X 的值，这样：节点 i 的值 ≤ 节点 i 的父节点的值, 我 = 2,3,...,nt。堆的大小是树中节点的数量。当且仅当它的大小为 0 时，堆是空的。

最大堆的定义是这样的，但对我来说似乎有点模棱两可。

4

3 回答 3

9

您需要在每次插入后显示生成的树。我的意思是，如果最初你有一个堆

   3
  / \
 1   2

然后插入一个 5，它将从最后一个堆位置开始，并会冒泡到堆头：

    3           5
   / \         / \
  1   2  =>   3   2
 /           /
5           1

类似地，如果你插入一个 4，那么：

    5           5
   / \         / \
  3   2  =>   4   2
 / \         / \
1   4       1   3
于 2012-11-25T19:57:16.477 回答
4

简而言之，最大堆是父项的值大于其任何子项的值的堆。当您绘制初始完整二叉树时，它是否已经采用最大堆的形式？筛选（在我的大学里，我们称它为起泡，但除此之外）在这样的线程上解释起来有点复杂，所以我同意@DanteisnotaGeek。维基百科文章很好地说明了筛选过程的工作原理。插入后显示最大堆要求您绘制二叉树，以便在每次插入后满足最大堆属性。所以最后，你应该有你的初始树，一棵树有你的第一个插入，第二个插入和第三个插入，所以总共有 4 棵树。

于 2012-11-25T17:10:22.573 回答
1

在堆中，在任何时刻，从根节点到叶节点都是有序且线性的：

在此处输入图像描述

当您将元素插入堆中的下一个插槽时，该行的顺序将被更改： 在此处输入图像描述

所以，插入的最后一步变成了对线性数据结构进行重新排序：冒泡排序

于 2018-03-24T02:03:01.657 回答