I have this 3 heap max heap that I need to write the array for it, but I'm not sure how. Would it just be


enter image description here

  • $\begingroup$ I think you just have to add the 10 1 in the end. $\endgroup$ – WhatsUp Oct 7 '19 at 6:24
  • $\begingroup$ yea I did that but it was wrong $\endgroup$ – Julie G Oct 7 '19 at 6:30
  • $\begingroup$ Otherwise I don't know what is "the array for it". I understand it as the array implementation of a ternary heap, as described here: en.m.wikipedia.org/wiki/D-ary_heap $\endgroup$ – WhatsUp Oct 7 '19 at 6:36

Yes, it would be Just the Level Order Traversal of the tree, In this case, it is 20,18,13,15,11,12,16,10,9,11,13,2,9,10,1.

More generally for a generalized d-heap, the items may be viewed as the nodes in a complete d-ary tree, listed in breadth-first traversal order: the item at position $0$ of the array (using zero-based numbering) forms the root of the tree, the items at positions 1 through d are its children, the next $d^2$ items are its grandchildren, etc. Thus, the parent of the item at position $i$ (for any $i > 0$) is the item at position $⌊(i − 1)/d⌋$ and its children are the items at positions $d\cdot i + 1$ through $d\cdot i + d$.

| cite | improve this answer | |
  • $\begingroup$ thank you! I think I entered some numbers wrong. $\endgroup$ – Julie G Oct 7 '19 at 7:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.