使用树实现堆

Question

关于这一点已经有很多问题(例如使用树实现堆)，但是没有一个问题有一个公认的答案。所以，我在这里再问一次，让问题更清楚。< br >二叉树已经实现，并且二叉树的私有内部类包括

    T element;
    Node<T> parent;
    Node<T> leftChild;
    Node<T> rightChild;

所以，我有元素，父，左孩子，右孩子的引用。
内部类包含每个获取器和设置器。
内部类正在实现位置

size()//Returns size of tree
parent(Position<T> node)//return Position<T> of parent of node
left(Position<T> node)//return Position<T> of leftChild of node
right(Position<T> node)//return Position<T> of rightChild of node
numChildren(Position<T> node)//to return number of children of node

更新方法包括

 addRoot(T element)//element will be added as root if tree is empty
 addLeft(Position<T> position,T element)//Left child to be added at position
 addRight(Position<T> position,T element)//right child to be added at position
 set(Position<T> position,T element)//Element of positon will be changed to
                      //element passed in pareameter and previous element will be returned
 remove(Position<T> position)// position will be removed



所以，现在关于堆

[编辑]：我正在使用适配器模式在堆中实现的二叉树类

访问最后一个位置，我从root开始，然后检查它是否具有正确的子项，然后继续直到有小于2的子项并返回该位置，如果它没有右子项，则从左侧子级继续，其余过程是相同的。
现在，我有一个或零个子级的位置，现在我可以检查该位置的左侧是否为空，因此请添加到左侧，否则添加到右侧。

现在添加后，我必须检查堆顺序属性，如果它不符合，我必须上堆，现在的问题是我无法更改父
级 注意：我无法向二叉树添加新方法




Answer 1

由于您在树中有一个大小（）方法，并且您知道树是平衡的，因此您可以计算最后一个位置。

          1
        /   \
      2       3
     / \     / \
    4   5   6   7
   /
  8  ...

就是二进制的

               1
            /      \
         10           11
        / \          /  \
      100  101    110    111
      / \
   1000  1001  ... 

要从根到给定位置，您可以删除二进制表示中的第一个“1”，然后使用剩余数字从根向左（代表0）或向右（代表1）行走。因此，对于大小6=0101，您重新移动第一个“1”，留下“01”，这意味着向左，然后向右。

另请参见这个问题，这个问题在C中解决。