Computer Science Canada

Heaps

Author:  A.J [ Tue Mar 18, 2008 2:58 pm ]
Post subject:  Heaps

Hello everyone!!
As I am more comfortable with Microsoft WORD, I attached the tutorial in Microsoft WORD.

Enjoy Very Happy

(P.S: it is kinda hurried, as I had other work to do. Please comment!)

Author:  A.J [ Tue Mar 18, 2008 4:20 pm ]
Post subject:  Re: Heaps

I'll try adding the sequel to this tutorial in about few days if people are willing to know more about it...

Author:  zylum [ Tue Mar 18, 2008 7:38 pm ]
Post subject:  RE:Heaps

A few things..

Parent nodes of heaps don't have to have 2 or zero children. They can also have 1 child so long as the binary tree is complete.

The insert procedure in your code is more like the 'swim' procedure or the more general 'hepify' procedure so the name is a bit misleading as it doesn't actually to any insertion, just restoring the properties of the heap.

Since turing allows for 1 based indexing of arrays, it is more convenient to create a heap with 1 as the first element. This way the child heap of node n is 2n and 2n+1 rather than 2n+1 and 2n+2.

Your example use of heaps is sort of confusing and I don't really see how a heap helps in this case. The true power of heaps is in the fact that you can find the min/max in O(1) time.

Sorry this reply is sort of rushed, i gotta get going. Ill make a more useful post when i get back later..

Author:  A.J [ Tue Mar 18, 2008 7:50 pm ]
Post subject:  Re: Heaps

I guess I should post a tutorial on something i am good at ................... Embarassed

Author:  zylum [ Tue Mar 18, 2008 11:13 pm ]
Post subject:  RE:Heaps

Writing a tutorial/teaching someone is one of the best ways to learn something. Also making mistakes helps in the learning process. Someone points out your error and thus you are more likely to remember your mistake.

Anyways, it's a good start. Keep it up. Make sure you point out how to create a heap in O(n) time although a formal proof of why it runs in O(n) time might be a bit tough for you. Some practical applications for motivation would be nice too. Heap sort for example becomes trivial once you know how heaps work Wink

Author:  A.J [ Tue Mar 18, 2008 11:35 pm ]
Post subject:  Re: Heaps

true....and it doesnt look like people are interested anyways....oh well I tried Crying or Very sad

Author:  Tony [ Wed Mar 19, 2008 12:01 am ]
Post subject:  Re: Heaps

A.J @ Tue Mar 18, 2008 2:58 pm wrote:
I attached the tutorial in Microsoft WORD.

It's fine if you want to type up you tutorials in Word, but please print to a PDF for distribution purposes.


: