Heap Data Structure

[TuX4020]

Hi all,

So I've got an assignment of creating a priority queue using a heap data structure. I've read lots of pages online about the heap data structure, but I keep coming up with questions.

In my class, I got the impression that a heap was structured similarly to a tree - parent node/child node type stuff. But the more I read online, it appears that the method of choice is fashioning a heap based on an underlying array - which way is generally preferred?

Because as I started to work through a tree based solution, I stumble trying to determine when I've found the left most opening for the bottom level of the tree to insert a new value in.

All that being said, absolutely any tips or advice about the underlying data structure for a priority queue would be greatly appreciated. I'm not really looking for code samples, just a push in the right direction. Many thanks!

[Clockowl]

If you're standing in queue line at the grocery shop, does the LINE look like a tree, with intersections and such, or more like an array of (possibly annoyed) customers?

I sure hope it doesn't look like a tree.

[ArkM]

http://www.cs.utsa.edu/~dj/ut/utsa/cs3343/lecture7.html
Yes, common priority queue implementations are based on heap data structure founded on a linear (as usually, in array) representation of a tree...
;)

[TuX4020]

The analogy makes complete sense. My teacher just doesn't give very specific objective for projects like this. So as he's drawing a priority queue out on the board he's just drawing it as a tree and never mentioned an array - so that's what initially gets stuck in my head.

But anyway, thanks for the quick reply. Now I can move on and just focus on an array as the underlying structure for my heap. Thanks for the help.

[Clockowl]

Good luck with the assignment, don't forget about the STL! (It has a queue, of course you can't use that, but it has plenty of other useful containers and algorithms).

[TuX4020]

So the linear representation of the tree would have node at index 0, would have 'children' at index 1 and 2. Node at index 1 would have 'children' at index 3 and 4 and so on and so on- correct?

[TuX4020]

Yeah I've come across the STL containers while I was researching to get started - but I think it would be best to work on my own implementation of it. That way at least I know how it works and then I can use the STL one with more insight.

[jrw0267]

with heaps you start at array index 1 because to find children of a node at position i

i*2 is the "left child"
i*2+1 is the "right child"

using quotes because it is implimented in an array but often pictured as a tree