13 Replies - 2277 Views - Last Post: 01 November 2011 - 10:59 AM Rate Topic: -----

#1 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Array representation of 3-heap

Posted 30 October 2011 - 10:52 AM

Hello,
I would like to know how to represent a 3-heap 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.

Is This A Good Question/Topic? 0
  • +

Replies To: Array representation of 3-heap

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2205
  • View blog
  • Posts: 5,239
  • Joined: 10-September 10

Re: Array representation of 3-heap

Posted 30 October 2011 - 01:13 PM

I don't think anyone understands your question or agrees with your premise. Yes, you're right in thinking that nodes of binary trees can have up to 2 children, typically referred to as 'left' and 'right'. Ternary trees can have 3 children. It isn't a requirement that children in either binary or ternary trees have a specific mathematical relationship to their respective parents; there is no required formula that relates children to their parents. There MAY be, if that's how your tree is defined, but that would be a specific implementation that would limit its usefulness.

If you're still pursuing this, please restate your question in a way we can help you.
Was This Post Helpful? 1
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,910
  • Joined: 06-March 08

Re: Array representation of 3-heap

Posted 30 October 2011 - 01:17 PM

View Postimu_1, on 30 October 2011 - 01:52 PM, said:

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.

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
Was This Post Helpful? 0
  • +
  • -

#4 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Array representation of 3-heap

Posted 30 October 2011 - 02:07 PM

guys, this is way of representing a binary heap. For more info, you can read mark allen weiss's book on Data Structures. All I was asking is a way to represent a 3-heap in an array.
Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,910
  • Joined: 06-March 08

Re: Array representation of 3-heap

Posted 30 October 2011 - 03:13 PM

View Postimu_1, on 30 October 2011 - 05:07 PM, said:

guys, this is way of representing a binary heap. For more info, you can read mark allen weiss's book on Data Structures. All I was asking is a way to represent a 3-heap in an array.

How would you reconstruct the Tree from that array ? I am anxious to see your algorithm
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Array representation of 3-heap

Posted 30 October 2011 - 06:59 PM

I'm gonna go out on a limb and say that 3i+1, 3i+2, and 3i+3 is probably the appropriate formula for accessing each of the children. Really, if you just think about it, then it makes perfect sense. Look for a pattern in how the binary heap is broken down into an array and try to apply that to your 3-Heap.

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.
Was This Post Helpful? 0
  • +
  • -

#7 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,910
  • Joined: 06-March 08

Re: Array representation of 3-heap

Posted 30 October 2011 - 07:02 PM

View Postmacosxnerd101, on 30 October 2011 - 09:59 PM, said:

I'm gonna go out on a limb and say that 3i+1, 3i+2, and 3i+3 is probably the appropriate formula for accessing each of the children.

Will work if the tree is perfectly balanced which is rarely the case
Was This Post Helpful? 0
  • +
  • -

#8 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Array representation of 3-heap

Posted 30 October 2011 - 07:38 PM

well, that will not work macos, even if the tree is balanced. I tried that and it didnt work. Just draw a 3-heap and apply the formula. It will work for the children of the root node but it will not work for the rest of the parent nodes. That's why i decided to seek help. This is an assignment so am sure there is a way to represent it in an array.
Was This Post Helpful? 0
  • +
  • -

#9 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,910
  • Joined: 06-March 08

Re: Array representation of 3-heap

Posted 30 October 2011 - 07:56 PM

As already said

View Postimu_1, on 30 October 2011 - 01:52 PM, said:

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.

Your premise is false
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Array representation of 3-heap

Posted 30 October 2011 - 10:32 PM

Yes, it will work. Remember that a Heap is a complete tree.
Posted Image

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 4-6 (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
Was This Post Helpful? 1
  • +
  • -

#11 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Array representation of 3-heap

Posted 31 October 2011 - 07:31 AM

yeah man, u r right. It works. My bad. ThANKX ALOT.
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Array representation of 3-heap

Posted 31 October 2011 - 07:33 AM

Glad I could help! :)
Was This Post Helpful? 0
  • +
  • -

#13 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Array representation of 3-heap

Posted 31 October 2011 - 07:41 AM

hey macos, if we wanna go from any child to its parent, then I believe this would work :

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

Was This Post Helpful? 0
  • +
  • -

#14 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Array representation of 3-heap

Posted 01 November 2011 - 10:59 AM

are my formulas sound correct ?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1