Results 1 to 19 of 19
  1. #1
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default heap sort question

    Can someone explain how the heap-sort algorithm would work on the sequence (16,4,8,10,12).

    with explanations of when the insertion and removal to the heaps are required and how they work.

    I cannot find anything useful online regarding this.

  2. #2
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    anyone?

  3. #3
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    noone

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    That is absolutely not how this works. This isn't google or a homework service. How do you think heap sort works? What have you tried? Where are you stuck?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    yes I've tried. I don't understand how to begin it. Do I begin it in the tree or can I put them one by one using the insertion sort?

  6. #6
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    Do you understand how heap sort works? If so, list the steps it takes and then apply those steps to your input. If not, do a google search of heap sort. I'm sure your class book is another valuable resource for an explanation.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  7. #7
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,534
    Blog Entries
    7
    Rep Power
    20

    Default Re: heap sort question

    I wrote a blog article on heap sort once (check the button near the top of this page). Heap sort works with two passes (or phases); the first phase constructs a heap out of a sequence of items and the second phase removes the largest element from the heap and corrects it again until the heap is empty. A big advantage is that it can do this all in place (no auxiliary memory is needed) and it can do it stable big-Oh wise.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    the way i was taught is that in the second phase it removes the smallest numbers first

  9. #9
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    Quote Originally Posted by stuckonjava View Post
    the way i was taught is that in the second phase it removes the smallest numbers first
    Either one works, because a heap can be a min-heap or a max-heap. I think most descriptions use a max-heap. The idea is the same though. But these little discrepancies are why I asked you to define heap sort's behavior. If you know how you've been taught, where exactly are you stuck?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  10. #10
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    I understand the heap sort perfectly, the problem I have is showing the first phase in terms of the list. For eg the list (16,4,8,10,12). How would I show the first phase of this step by step. I can do it using a binary tree but whats the best way to present this without one?

  11. #11
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    If you understand heap sort perfectly, I don't know what you're confused about. What is step one in heap sort? What is the first thing that would be done with that input?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  12. #12
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    ok the first thing would be to put 16 as the root, then the 4 as its left child, but as 4 is smaller than 16 they swap. The 8 would now become the right child of 4, the 10 would become the left child of 16 and swap places with it. The 12 would then become the right child of 10.

  13. #13
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    If that's the way you were taught, okay. Like I said, most descriptions reverse that.

    So what comes next?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  14. #14
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    the 4 would be put into the new sorted list(forgot what it is called), and 12 becomes the new root , the 12 and 8 now swap places making 8 the new root. The 8 is nwow put into the new list along wth the 4. 16 now becomes the root, and swaps places with 10 which is then sent into the list with 4 and 8. 12 becomes the new root and is sent into the list with 4,8,10. Now only 16 is left and as there is nothing to compare it with it is sent into the sorted list whose contents now consist of 4,8,10,12,16.

  15. #15
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    Actually, I think the extraction is a little more involved than 12 magically becoming the new root. In the descriptions I'm familiar with, the last child is swapped with the root and then the old root is removed, and the new root is "trickled down" to maintain the heap.
    Last edited by KevinWorkman; 03-15-2012 at 02:49 PM.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  16. #16
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    Oh, my description was that once the smallest key is the root it is remove into the new list.

  17. #17
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    If that's your description, okay, but I'm working from the description I've been familiar with, which is also on wikipedia: Heapsort - Wikipedia, the free encyclopedia

    A possible minimum is temporarily set as the root, but only to extract the actual root, which is the max. It could be that your teacher is taking a slightly different approach with heap sort, or it could be that you're misunderstanding a step to mean that the heap is a min-heap. I can't be sure which one is the case.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  18. #18
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: heap sort question

    I though one of the heap rules was that node(v) >= node(v).parent

  19. #19
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,964
    Rep Power
    8

    Default Re: heap sort question

    Like I said, it really depends on the details of your implementation. There is a chance you're being given a slightly modified heap sort that uses the same idea in a different way. But the "traditional" approach to heap sort is to use a max-heap, where a parent is greater than any of its children (so the opposite of what you're saying). I'm not in your class though, so I really can't say for certain whether that's the case or you're simply confusing something.

    Either way though, you're going to want to more fully understand what happens when you take the root out of your heap.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. heap sort help
    By aizen92 in forum Advanced Java
    Replies: 5
    Last Post: 12-05-2011, 03:33 PM
  2. Heap Sort
    By sehudson in forum New To Java
    Replies: 8
    Last Post: 03-31-2011, 03:25 AM
  3. Question with bubble sort
    By Metastar in forum New To Java
    Replies: 22
    Last Post: 09-13-2010, 06:25 AM
  4. Heap Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-16-2008, 10:27 PM
  5. Heap Sort
    By kesav2005 in forum Advanced Java
    Replies: 1
    Last Post: 11-13-2007, 11:40 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •