Heap Implementation Using Tree

Question

There are already many questions on this (i.e. Implementation of Heap using Tree) but none of them has an accepted answer. So, I am asking it again here by making question more clear.
Binary Tree is already implemented and private inner class of binary tree include

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

So, I am having reference of element, parent, leftChild, rightChild.
Inner class contains every getter and setter.
Inner class is implementing Position<T> interface which has only one method getElement()

BinaryTree has following accessor methods

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

Update Methods include

 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

So, Now Regarding Heap

[Edit]: I am using implemented Binary Tree class in heap by adapter pattern

To access last Position, I started from root then check if it has right Child, then continue until there are children less than 2 and return that position, if it does not have right child , continue from left child and rest of process is same.
Now, I have position which has one or zero child, now I can check if left of that position is null, so add to left otherwise to right side.

Now After adding I have to check Heap-Order Property, If it does not met I have to Up-Heap, Now issue is that I am unable to change the parent
Note: I can not add new methods to Binary Tree

You should draw the binary tree with several sizes to see that you cannot find the last Position like that. Even if root has a right child, the last position might be on the left. — tkruse, Mar 13 '18 at 07:48
Possible duplicate of [Binary Heap Implemented via a Binary Tree Structure](https://stackoverflow.com/questions/7609047/binary-heap-implemented-via-a-binary-tree-structure) — tkruse, Mar 13 '18 at 07:51
In my opinion, an additional pointer to the parent would ease the implementation. Even so, I think is hard to implement. I have a full and tested implementation in C++, if you are interested, please let me know and I post a summary with a link pointing to the code. — lrleon, Mar 13 '18 at 21:38

tkruse · Answer 1 · 2018-03-13T08:07:16.397

Since you have a size() method in the tree, and you know the tree is balanced, you can calculate the last position.

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

In binary, that is

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

To get from the root to a given position, you can remove the first '1' in the binary representation, then use the remaining digits to walk either left (for 0) or right (for 1) from the root. So for size 6 = 0101, you remmove the 1st '1', leaving you with '01', which means go left, then right.

Also see this question where this problem is solved in C.

Heap Implementation Using Tree

1 Answers1