P: n/a

I'm not sure this is technically a c++ question, maybe there is a better ng
to ask, but I'll start here since I'm coding this in c++. What exactly is a
max heap, and more specifically, how do you inert into one? I've looked at
faq, several books, and but am not quite understanding that algorithm to
insert into max heap.  
Share this Question
P: n/a

Ook wrote: I'm not sure this is technically a c++ question, maybe there is a better ng to ask, but I'll start here since I'm coding this in c++. What exactly is a max heap, and more specifically, how do you inert into one? I've looked at faq, several books, and but am not quite understanding that algorithm to insert into max heap.
A heap is an implementation of a priority queue (PQ) which is itself an
abstract data structure that supports operations including (supposing
that we are holding ints):
void push(int value); // inserts value into the PQ
int top(); // returns largest value in the PQ
void pop(); // removes largest value from the PQ
The standard library has a priority queue called priority_queue
(technically this is an adaptor because it builds priority_queue
behavior on top of an underlying container such as a vector). http://www.sgi.com/tech/stl/priority_queue.html
That site has a description of the class as well as a short example
showing its usage.
Mark  
P: n/a

"Mark P" <fa******@REMOVEfall2005.CAPSfastmail.fm> wrote in message
news:49******************@newssvr12.news.prodigy.c om... Ook wrote: I'm not sure this is technically a c++ question, maybe there is a better ng to ask, but I'll start here since I'm coding this in c++. What exactly is a max heap, and more specifically, how do you inert into one? I've looked at faq, several books, and but am not quite understanding that algorithm to insert into max heap.
A heap is an implementation of a priority queue (PQ) which is itself an abstract data structure that supports operations including (supposing that we are holding ints):
void push(int value); // inserts value into the PQ int top(); // returns largest value in the PQ void pop(); // removes largest value from the PQ
The standard library has a priority queue called priority_queue (technically this is an adaptor because it builds priority_queue behavior on top of an underlying container such as a vector).
http://www.sgi.com/tech/stl/priority_queue.html
That site has a description of the class as well as a short example showing its usage.
Mark
That is helpfull, but what I'm really after is how the values are
represented in the heap  what order they are in, where they would appear,
etc. IE if I had a string of numbers, how can I tell how those numbers would
be represented in the tree?  
P: n/a

Ook wrote: "Mark P" <fa******@REMOVEfall2005.CAPSfastmail.fm> wrote in message news:49******************@newssvr12.news.prodigy.c om...
Ook wrote:
I'm not sure this is technically a c++ question, maybe there is a better ng to ask, but I'll start here since I'm coding this in c++. What exactly is a max heap, and more specifically, how do you inert into one? I've looked at faq, several books, and but am not quite understanding that algorithm to insert into max heap.
A heap is an implementation of a priority queue (PQ) which is itself an abstract data structure that supports operations including (supposing that we are holding ints):
void push(int value); // inserts value into the PQ int top(); // returns largest value in the PQ void pop(); // removes largest value from the PQ
The standard library has a priority queue called priority_queue (technically this is an adaptor because it builds priority_queue behavior on top of an underlying container such as a vector).
http://www.sgi.com/tech/stl/priority_queue.html
That site has a description of the class as well as a short example showing its usage.
Mark
That is helpfull, but what I'm really after is how the values are represented in the heap  what order they are in, where they would appear, etc. IE if I had a string of numbers, how can I tell how those numbers would be represented in the tree?
That's entirely an implementation detail and in general there's no way
to know unless you know exactly how the code operates behind the scenes.
The "heap property" specifies that the root of the tree is the largest
element and, more generally, that every element in the tree (which
should be balanced, btw) is greater than all of it descendants.
For example, a heap with the numbers 1 2 3 4 5 could look like:
5
/ \
4 1
/ \
2 3
or,
5
/ \
4 3
/ \
2 1
or,
5
/ \
3 4
/ \
1 2
etc...  
P: n/a
 That's entirely an implementation detail and in general there's no way to know unless you know exactly how the code operates behind the scenes. The "heap property" specifies that the root of the tree is the largest element and, more generally, that every element in the tree (which should be balanced, btw) is greater than all of it descendants.
For example, a heap with the numbers 1 2 3 4 5 could look like:
5 / \ 4 1 / \ 2 3
or,
5 / \ 4 3 / \ 2 1
or,
5 / \ 3 4 / \ 1 2
etc...
Ahh..I think that is the key  that the root is the largest element. Would I
be correct to describe it like a BST, but not necessarily strictly sorted?  
P: n/a

Ook wrote: That's entirely an implementation detail and in general there's no way to know unless you know exactly how the code operates behind the scenes. The "heap property" specifies that the root of the tree is the largest element and, more generally, that every element in the tree (which should be balanced, btw) is greater than all of it descendants.
For example, a heap with the numbers 1 2 3 4 5 could look like:
5 / \ 4 1 / \ 2 3
or,
5 / \ 4 3 / \ 2 1
or,
5 / \ 3 4 / \ 1 2
etc...
Ahh..I think that is the key  that the root is the largest element. Would I be correct to describe it like a BST, but not necessarily strictly sorted?
Well, sort of that's a bit contradictory since you can't really search
(the 'S' in BST) if it isn't sorted, but I think you get the idea. You
really ought to look up an implementation of a heap by only requiring
that each element is larger than its descendants it's much simpler to
maintain a balanced tree than a sorted balanced BST (e.g. a redblack tree).   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 10176
 replies: 5
 date asked: Nov 22 '05
