Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Heaps
Author Message
A.J

Posted: 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

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

HEAPS.doc
Description:
 here it is!!

Filename:  HEAPS.doc
Filesize:  58.5 KB

A.J

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

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

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

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

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
Tony

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.
Tony's programming blog. DWITE - a programming contest.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 7 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: