Implement Heap using a Binary Tree
This question has been asked before in Stack Exchange but it went unanswered.
Link to the previously asked question: Binary Heap Implemented via a Binary Tree Structure
How do I implement heap in a binary tree. To implement heap, it is important to know the last filled node and the first unoccupied node. This could be done in level ordering of the tree, but then the time complexity will be O(n) just to find the first unoccupied node. So, how to implement heap in a binary tree in O(logn)?
Thanks Shekhar
Answer
To implement a heap with a binary tree with O(log n) time complexity, you need to store the total number of nodes as an instance variable.
Suppose we had a heap of 10 total nodes.
If we were to add a node...
We increment the total number of nodes by one. Now we have 11 total nodes. We convert the new total number of nodes (11) to its binary representation: 1011.
With the binary representation of the total nodes (1011), we get rid of the first digit. Afterwards, we use 011 to navigate through the tree to the next location to insert a node in. 0 means to go left and 1 means to go right. Therefore, with 011, we would go left, go right, and go right...which brings us to the next location to insert in.
We examined one node per level, making the time complexity O(log n)