(10)
/ \
(9) (8)
/ \ / \
(7) (5) (4)
x x
/ and \ == x=>y
y y
thanks in advance
views:
185answers:
2
+5
A:
That looks like a max-heap, except that (5) should not be attached to two parents.
A max-heap is a tree-based data structure where x>=y if x is a parent of y. Since it is a tree, each child can only have one parent.
interjay
2010-02-08 20:11:33
What's this "should not" business? As shown, it's a perfectly valid structure. It may just not be a max-heap.
ceejayoz
2010-02-08 20:21:18
I meant that if it is a max-heap then a child should not be attached to two parents. I still think that the instructor had meant a heap.
interjay
2010-02-08 20:23:43
+5
A:
It's a directed acyclic graph (DAG), which can define a (partial) ordering relation.
Wim
2010-02-08 20:12:28
well , if (5) is a child of (9) and (8), then it is cyclic. But that might have been a typo by the OP... not sure.
FrustratedWithFormsDesigner
2010-02-08 20:13:22
@Fru: From his `x=>y` comment I understand that he means a *directed* graph, with all edges running down. You don't have a cycle that way, since once you reach (5) you cannot go up again.
Wim
2010-02-08 20:16:00
@FrustratedWithFormsDesigner: He seems to have defined a direction (x=>y), so it's not cyclic.
3lectrologos
2010-02-08 20:16:18
Actually, I see nothing to indicate direction, either.
FrustratedWithFormsDesigner
2010-02-08 20:16:27
Ah, never mind. I thought he mean to type `>=` instead of `=>` so I did not interpret it the same way.If that's how he meant it then yes, DAG is correct.
FrustratedWithFormsDesigner
2010-02-08 20:17:26
I think we can all agree that as it currently is, there's multiple contradicting intepretations...
FrustratedWithFormsDesigner
2010-02-08 20:18:31
sorry everyone, I was just curious if this structure actually existed, but maybe my instructor made this up himself
Shellscriptbeginner
2010-02-08 20:21:19