Hi, if anyone's an expert on this topic, can you post - thanks

you should post your question.

in c++ any time the `new` keyword is used it allocates memory on the heap else it's allocated on the stack.

what is your question?

can someone explain to me the difference between a binary tree and a heap? Lol

binary tree is simply an acyclic graph where each node has at most two children. no ordering is implied.

a heap is a tree where the relative ordering between parent and child remains constant; eg if the parent >= child, it's a max heap. for one thing, a heap can have more than two children so it doesn't have to be a binary tree at all. a binary heap is a binary tree - like structure that satisfies the heap property i already mentioned.

This post was edited by carteblanche on Feb 3 2013 11:04pm

relative ordering between parent and child remains constant.....so in a max heap, the children will ALWAYS be less than/equal to the parent?

This post was edited by Eep on Feb 3 2013 11:15pm

do you understand how a max heap works? tell me what the performance is for removing/adding and explain how you acheive that performance.

I know they are built from complete binary trees apparently, then they sift the values down

I know that sifting down uses no more than big O of Log (n)



This post was edited by Eep on Feb 3 2013 11:35pm

explain it in more detail until you understand it. how is it that a peak is constant time and insert/delete are logarithmic? then answer the question you asked me.

peek just finds the root, so it is O(1)

Insert/delete however are based on the number of levels of the heap, therefore the time complexity is O(Log(n))

for delete you have to take the last element on the last level and replace it with the previous root, then you have to make sure it is in the correct order

This post was edited by Eep on Feb 3 2013 11:55pm