3
$\begingroup$

Question:

Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data structure? Where would the duplicates of other integers reside in the heap?

My Answer: The duplicates can reside below (as children of) the value considering a heap (tree structure). Or if we are using arrays to implement this Max Heap, then the duplicates would reside on the indices H[2i + 1] and H[2i + 2] where i is the index of the parent node.

Or we can even make a pointer to a link list of duplicates from that node which has duplicates.

The teacher said that there is another way.

Could you please give me hints on how to do it? Or at least how to answer this question?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What if you have three, four, ... copies of the same key? Do you have data associated with the keys, or do you store plain numbers? $\endgroup$ – Raphael♦ Dec 16 '14 at 22:37
  • $\begingroup$ I'm not sure; I wrote the question as is. So you're suggesting that I store how many duplicates there are for the same key? Alright. Seems legit. Thanks $\endgroup$ – oaksndac Dec 16 '14 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.