What is Max Heap, how to insert

[Ook]

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.

 

[Mark P]

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

 

[Ook]

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?

 

[Mark P]

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

 

[Ook]

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?

 

[Mark P]

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 red-black tree).