Implement a heap not using an array

Question

I'm prepping for a Google developer interview and have gotten stuck on a question about heaps. I need to implement a heap as a dynamic binary tree (not array) where each node has a pointer to the parent and two children and there is a global pointer to the root node. The book asks "why won't this be enough?"

How can the standard tree implementation be extended to support heap operations add() and deleteMin()? How can these operations be implemented in this data structure?

Answer 1

Can you keep the size of total nodes ? if so, it's easy to know where you should add new element, because that's an almost full tree.

About deleteMin, I think that it will be less effective because you can't access directly to all leaves, as in array (N/2). You should travel through all paths till you get leaf and then compare them, probably it will cost O(n)