Array representation of 3heap
Page 1 of 113 Replies  2326 Views  Last Post: 01 November 2011  10:59 AM
#1
Array representation of 3heap
Posted 30 October 2011  10:52 AM
I would like to know how to represent a 3heap into an array. I know how to represent a binary heap.
For example, if I have 8
/ \
12 19
/ \ /
30 14 40
Then the array representation would be arr[1] = 8, arr[2] = 12, arr[3] = 19. Which means if I want a a left child, I will multiply my position by two. If I want a right child, I will do so by multiplying by two and adding a one.
So, how would you do it if you have three children per node. What would be the formula. I tried to represent the right most child with 2p + 2 ( where p is a position of parent), but it backfired bacause it is not applicable with all right most children.
Replies To: Array representation of 3heap
#2
Re: Array representation of 3heap
Posted 30 October 2011  01:13 PM
If you're still pursuing this, please restate your question in a way we can help you.
#3
Re: Array representation of 3heap
Posted 30 October 2011  01:17 PM
imu_1, on 30 October 2011  01:52 PM, said:
I have serious concerns about this statement. Is it imu_1's third rule of tree/array ? Where did you get this algorithm from ?
Really don't see how to translate a tree into an array
#4
Re: Array representation of 3heap
Posted 30 October 2011  02:07 PM
#5
Re: Array representation of 3heap
Posted 30 October 2011  03:13 PM
imu_1, on 30 October 2011  05:07 PM, said:
How would you reconstruct the Tree from that array ? I am anxious to see your algorithm
#6
Re: Array representation of 3heap
Posted 30 October 2011  06:59 PM
A lot of data structures are very interrelated, so understanding how to apply an algorithm from one to another is especially helpful in this area, as well as programming and CS in general.
#7
Re: Array representation of 3heap
Posted 30 October 2011  07:02 PM
#8
Re: Array representation of 3heap
Posted 30 October 2011  07:38 PM
#9
Re: Array representation of 3heap
Posted 30 October 2011  07:56 PM
imu_1, on 30 October 2011  01:52 PM, said:
Your premise is false
#10
Re: Array representation of 3heap
Posted 30 October 2011  10:32 PM
So that array would be: [45, 41, 42, 35, 29, 38, 34, 22, 11, 40, 9, 18]. So 45 is the root, index 0. The 3i+1 element is 41. Now 41's children are elements 46 (3(1) + 1, 3(1) + 2, 3(1) + 3). Yes, the formula does work. If "it doesn't work", that means your implementation is incorrect.
My source for the image: https://users.cs.jmu...ntroduction.php
#11
Re: Array representation of 3heap
Posted 31 October 2011  07:31 AM
#12
Re: Array representation of 3heap
Posted 31 October 2011  07:33 AM
#13
Re: Array representation of 3heap
Posted 31 October 2011  07:41 AM
left child to parent: i/3
middle child to parent: i/3
right child to parent: i/3 1
I thought its gonna be only one formula that would lead us to the parent, since its a same parent. But when I was going thru the tree, I realized that it doesnt work for the right child.
This post has been edited by imu_1: 31 October 2011  07:43 AM
#14
Re: Array representation of 3heap
Posted 01 November 2011  10:59 AM
