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!

7 Years
Discussion Span
Last Post by jrw0267

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.


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.


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


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?


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.


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

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.