Heap Sort

This is a discussion on Heap Sort within the C++ Programming forums, part of the General Programming Boards category; Hi everyone I am having a little problem with a heap sort code that I am writing. I have found ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    Heap Sort

    Hi everyone I am having a little problem with a heap sort code that I am writing. I have found a few templates that all looked the same but am having problems writing it on my own because I do not understand them completely. I completely understand how the heap sort algorithm works in theory and can draw out what happens using a binary tree. When implemented in code however I do not understand certain declarations like (root*2). I just wish I had a better picture of it. Please let me know if anyone can explain this or can direct me to a book or website that has an explanation of it.

    Thanks

    Code:
    void heapSort(int numbers[], int array_size)
    {
      int i, temp;
    
      for (i = (array_size / 2)-1; i >= 0; i--)
        siftDown(numbers, i, array_size);
    
      for (i = array_size-1; i >= 1; i--)
      {
        temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        siftDown(numbers, 0, i-1);
      }
    }
    
    
    void siftDown(int numbers[], int root, int bottom)
    {
      int done, maxChild, temp;
    
      done = 0;
      while ((root*2 <= bottom) && (!done))
      {
        if (root*2 == bottom)
          maxChild = root * 2;
        else if (numbers[root * 2] > numbers[root * 2 + 1])
          maxChild = root * 2;
        else
          maxChild = root * 2 + 1;
    
        if (numbers[root] < numbers[maxChild])
        {
          temp = numbers[root];
          numbers[root] = numbers[maxChild];
          numbers[maxChild] = temp;
          root = maxChild;
        }
        else
          done = 1;
      }
    }

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    no time to explain now so just look over this applet
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 05:03 AM
  2. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 04:54 AM
  3. How do I heap sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 7
    Last Post: 12-12-2007, 01:00 AM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21