# Array representation of 3-heap

Page 1 of 1

## 13 Replies - 1740 Views - Last Post: 01 November 2011 - 10:59 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=253505&amp;s=7be17087b3b02684caf9e7bf386db2d8&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 imu_1

• D.I.C Regular

Reputation: -6
• 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

• D.I.C Lover

Reputation: 2198
• Posts: 5,226
• 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.

### #3 pbl

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

Reputation: 8329
• Posts: 31,857
• Joined: 06-March 08

## Re: Array representation of 3-heap

Posted 30 October 2011 - 01:17 PM

imu_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

### #4 imu_1

• D.I.C Regular

Reputation: -6
• 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.

### #5 pbl

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

Reputation: 8329
• Posts: 31,857
• Joined: 06-March 08

## Re: Array representation of 3-heap

Posted 30 October 2011 - 03:13 PM

imu_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

### #6 macosxnerd101

• Self-Trained Economist

Reputation: 10486
• Posts: 38,857
• 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.

### #7 pbl

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

Reputation: 8329
• Posts: 31,857
• Joined: 06-March 08

## Re: Array representation of 3-heap

Posted 30 October 2011 - 07:02 PM

macosxnerd101, 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

### #8 imu_1

• D.I.C Regular

Reputation: -6
• 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.

### #9 pbl

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

Reputation: 8329
• Posts: 31,857
• Joined: 06-March 08

## Re: Array representation of 3-heap

Posted 30 October 2011 - 07:56 PM

imu_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.

### #10 macosxnerd101

• Self-Trained Economist

Reputation: 10486
• Posts: 38,857
• 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.

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

### #11 imu_1

• D.I.C Regular

Reputation: -6
• 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.

### #12 macosxnerd101

• Self-Trained Economist

Reputation: 10486
• Posts: 38,857
• Joined: 27-December 08

## Re: Array representation of 3-heap

Posted 31 October 2011 - 07:33 AM

### #13 imu_1

• D.I.C Regular

Reputation: -6
• 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

### #14 imu_1

• D.I.C Regular

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

## Re: Array representation of 3-heap

Posted 01 November 2011 - 10:59 AM

are my formulas sound correct ?