Member Avatar for 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!

  • 4 Contributors
  • 7 Replies
  • 134 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by jrw0267
Member Avatar for 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.

Member Avatar for 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.

Member Avatar for 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).

Member Avatar for 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?

Member Avatar for 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.

Member Avatar for 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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.