Posted: 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...
Posted: 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..
Posted: Tue Mar 18, 2008 7:50 pm Post subject: Re: Heaps
I guess I should post a tutorial on something i am good at ...................
Posted: 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
Posted: 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
Posted: 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.