题目：

Implements the insertion into a priority queue with smallest elements being of highest priority as a binary tree.

---

题目大意：

插入数据构建一个小顶堆。小顶堆实质上是一个二叉树，只是根结点必须小于它的后代结点，以此类推。

输入输出示例：

输入输出示例

---

思路：

小顶堆实质上是一个完全二叉树。因此我们可以将新加入进来的结点加入到这个完全二叉树中然后在调整这个完全二叉树。

例如，我们现在有[2, 0, 3]这样一个堆，如图所示：

图1

此时我们需要插入一个结点1。如下图所示：

图2

之后我们需要做的就是调整这个堆，由于我们要创建的是小顶堆，1比2要小所以我们需要交换结点1和2的位置。

图3

以上是创建一个小顶堆的过程。

首先我们面对的一个问题是如何找到插入结点的位置。根据完全二叉树的性质每一层结点的数目是2^（n-1）（n代表结点所在的层数）。然后在计算二叉树目前包含的结点的数目size。使用二叉树的层次遍历，记录二叉树在每一层的结点数目（m），每遍历一层就改变size的数目——size-m。一旦size小于之后一层应该有的结点数的时候，就说明咱们需要找的结点（将目标结点插入的结点）就在接下来的这一层。

之后就是在下一层中找到目标结点。由于已经记录这一层的结点在Queue中，我们就遍历Queue中的结点，每遍历一个结点就改变size的值——size-2。为何减2，因为目标结点之前的结点都有两个子结点。一旦size的值小于0，就说明我们找到了目标结点。

之后的任务就是插入新的值，这个很简单，如果左结点为空就插入到左结点中，否则插入到右结点中。

最后的一个问题就是调整堆使其变成小顶堆的问题了。首先每个插入到堆（二叉树）中的结点都有一个序号，调整堆就需要找到它的根结点。假设一个结点的序号为n，则它的根结点为n // 2。一旦此结点的值大于它的根结点则交换这两个结点的位置。注意在之前层次遍历的时候需要新建一个队列记录待插入结点之前各层的结点。因为调整堆的时候需要使用到这个队列。也是通过序号n在这个队列中找需要比较的结点。

---

代码：