Thread: max heapify and build max_heapify algorithm doesn't work as expected.

  1. #1
    Registered User
    Join Date
    Nov 2011
    Location
    Buea, Cameroon
    Posts
    197

    Post max heapify and build max_heapify algorithm doesn't work as expected.

    heyt guys i wrote this program from the pseudocode and this does not this thing has been giving me stress for days now.....need help........
    Code:
    //FileName: Max_heapify.c
    //Author: Nyah Check, Chairman @ INK Corp.
    //This program illustrates the Max _heapify algorithm for sorting numbers.
    //Usage: This is a freeware and should be licenced following the GNU Public licence.
    //INK Corp. 2012.
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #include <assert.h> //this header checks for errors with the  algorithm.
    
    #define HEAPSIZE(A) sizeof(A)/sizeof(int) //determines the heap size which is <= sizeof(A).
    #define LEFT(i) i<<1          // this macro doubles i.
    #define RIGHT(i) (i<<1) + 1   //this macro computes 2(i) + 1.
    #define PARENT(i) i>>1        //this macro computes the floor(i/2).
    
    int MAX_HEAPIFY(unsigned int A[], unsigned int n);
    int BUILD_MAX_HEAP(unsigned int A[]);
    
    unsigned int A[] = {27, 17, 3, 16, 13, 10, 1,5 , 7, 12, 4, 8, 9, 0};
    unsigned int i, largest;
    
    int main(void)
    {
       unsigned int m = 0;
    
        printf("\nThis program sorts input in decreasing order using the Max_heapify algorithm.");
    
        printf("\nOriginal Array: ");
        for ( unsigned int i = 0; i < HEAPSIZE(A); i++)
            printf(" %d ", A[i]);
    
        //printf("\nImplementing Heap sort.....");
        /*for ( t = 0, q = 1; t < HEAPSIZE(A)/2; t++, q++)
            MAX_HEAPIFY(A, t);
            assert(k); //this checks for the return value of the MaxHeap algo.
         *
         */
         BUILD_MAX_HEAP(A);
    
        printf("\nFinal Array: ");
        errno = HEAPSIZE(A);
        for ( m = 0; m < HEAPSIZE(A); m++)
            printf(" %d ", A[m]);
    
        if ((int)m > errno)  //this checks whether the loop read past the end of array.
            fprintf(stderr, "Final heap Error: function read past end of array.");
            exit(EXIT_FAILURE);
    
        return 0;
    }
    
    //This function uses the max heapify algo to sort numbers in an array.
    int MAX_HEAPIFY(unsigned int A[], unsigned int n)
    {
        unsigned int l, r;
        l = LEFT(n);
        r = RIGHT(n);
        largest = n;
    
        if (l <= HEAPSIZE(A) && A[l] > A[n])
        {
            largest = l;
        }
    
        else if ( r <= HEAPSIZE(A) && A[r] > A[largest])
        {
            largest = r;
        }
    
        else if( largest != n)
        {
            i = A[n];
            A[n] = A[largest];
            A[largest] = i;
            MAX_HEAPIFY(A, largest);
        }
    
        return 1;
    }
    
    //This program calls the heap_max function recursively to sort the numbers.
    int BUILD_MAX_HEAP(unsigned int A[])
    {
        int i, z;
        z = HEAPSIZE(A);
        printf("\nTotal heap: %d ", z);
    
        for ( i = z / 2; i < z +1; i++)
        {
            printf("\nI: %d", i);
            MAX_HEAPIFY(A, i);
            printf("\nExecuted correctly.\n");
        }
    
        return 1;
    }

  2. #2
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    Code:
       if (l <= HEAPSIZE(A) && A[l] > A[n])
        {
            largest = l;
        }
     
        else if ( r <= HEAPSIZE(A) && A[r] > A[largest])
        {
            largest = r;
        }
     
        else if( largest != n)
        {
            i = A[n];
            A[n] = A[largest];
            A[largest] = i;
            MAX_HEAPIFY(A, largest);
        }
    change that 'else if' to 'if', you may have no chance to make recursive call with the 'else if'
    "All that we see or seem
    Is but a dream within a dream." - Poe

  3. #3
    Registered User
    Join Date
    Nov 2011
    Location
    Buea, Cameroon
    Posts
    197
    thanks @hunter i'll check that to see what it gives.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You don't seem to understand what a heap is. Your program says that it will sort the array, but all it then does is tries to build a heap.

    A heap does not normally equate to sorted order!

    Heap sort actually has one extra step, the progressive extraction of one item at a time from the heap until the heap is empty.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Nov 2011
    Location
    Buea, Cameroon
    Posts
    197
    so since i see some interchanging of figures in the Max heapify function i thought there would be a change in the array.

  6. #6
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    • No idea what you're doing with errno, especially because you aren't including <errno.h>. Either way, it's not a register that you can shove random variables into, so use it as intended.
    • You shouldn't be using globals.
    • For good practice, you should change your HEAPSIZE macro to
      Code:
      #define HEAPSIZE(A) (sizeof(A)/sizeof(A[0]))
      This ensures that it will work no matter what type "A" is, and putting parentheses around macro expressions is a good habit.
    • I'm not an expert with heaps, but nothing in your code seems to be sorting the values.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Nyah Check View Post
    so since i see some interchanging of figures in the Max heapify function i thought there would be a change in the array.
    Oh it'll swap items around alright. It's just not "sorted" order that it places them in. It's some other strange but useful ordering that it places items in.
    Go and search the net and learn about heaps. Perferably find something that shows an animation of heap operations.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Code:
    int BUILD_MAX_HEAP(unsigned int A[])
    {
        int i, z;
        z = HEAPSIZE(A);
        printf("\nTotal heap: %d ", z);
    I'd expect problems here. A is a pointer when you pass it as a function parameter like this, and sizeof (ptr)/sizeof(int) in this case isn't the number of elements in the array.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 12-07-2010, 06:53 AM
  2. cin.get(); doesn't seem to be working as expected
    By Diablo84 in forum C++ Programming
    Replies: 5
    Last Post: 03-30-2005, 07:00 PM
  3. Program doesn't always do whats expected... any ideas? (newbie)
    By photoresistor in forum C++ Programming
    Replies: 4
    Last Post: 12-07-2002, 02:49 AM
  4. Why this do-while loop doesn't work as I expected?
    By Nutka in forum C Programming
    Replies: 4
    Last Post: 10-25-2002, 09:47 AM