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.

# Array representation of 3-heap

Page 1 of 1## 13 Replies - 4154 Views - Last Post: 01 November 2011 - 10:59 AM

##
**Replies To:** Array representation of 3-heap

### #2

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

If you're still pursuing this, please restate your question in a way we can help you.

### #3

## 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

## 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

## 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

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

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 3-heap

Posted 30 October 2011 - 07:02 PM

### #8

## 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

## Re: Array representation of 3-heap

Posted 30 October 2011 - 07:56 PM

As already said

Your premise is false

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.

Your premise is false

### #10

## 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

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

## 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

## Re: Array representation of 3-heap

Posted 31 October 2011 - 07:33 AM

Glad I could help!

### #13

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

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 3-heap

Posted 01 November 2011 - 10:59 AM

are my formulas sound correct ?

Page 1 of 1