最大堆和插入

Question

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

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

定义(最大堆)HEAP(X)设X是一个完全有序的集合.X上的堆是空的,∅,或者它是一个完整的二叉树,t,包括nt≥1个节点到每个节点,其中X的值被分配,使得:节点i的值≤节点i的父节点的值,i = 2,3,...,nt.堆的大小是树中的节点数.当且仅当其大小为0时,堆为空.

max heap的定义是这样的,但对我来说看起来有点模棱两可.

Answer 1

您需要在每次授权后显示生成的树.我的意思是,如果最初你有一堆

   3
  / \
 1   2

并且你插入一个5,它将从最后一个堆位置开始,并将冒泡到堆头:

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

类似地如果你插入一个4,那么:

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