Heapify

This is a discussion on Heapify within the C++ Programming forums, part of the General Programming Boards category; I've tried to make a few different heapify functions, but none of them have worked. Why isn't this actually doing ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    15

    Heapify

    I've tried to make a few different heapify functions, but none of them have worked. Why isn't this actually doing anything?

    Code:
    void heapify(int array[], int i) {
        int largest = 0;
        int temp = 0;
        int n = sizeof(array);
        int l = left(i);
        int r = right(i);
        if (l <= n && array[l] > array[i]) {
            cout << "\n\nHERE IS THE DAMN PROBLEM";
            largest = l;
        }
        else {
            cout << "\n\nOkay, the else statement is working.";
            largest = i;
        }
        if (r <= n && array[i] > array[largest]) {
            cout << "\n\nOkay, largest = r.";
            largest = r;
        }
        if (largest != i) {
            cout << "\n\nAlright, this got down to the last step.";
            temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
            heapify(array, largest);
        }
    
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,418
    > int n = sizeof(array);
    Are you expecting this to tell you how many elements there are in an array?

    It's just telling you the size of the pointer (to the start of the array).

    You need to pass the actual size of the array as another parameter.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,411
    Quote Originally Posted by Salem View Post
    You need to pass the actual size of the array as another parameter.
    Or you can do
    template<typename N>
    void foo(int arr[N])

    Or even
    template<typename N>
    void foo(int (&arr)[N])
    (Not tested)

    Where you will have N as the size of your array.
    You will likely get a compile error if you try to pass in a pointer, so you're all set.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by Elysia
    Or even
    template<typename N>
    void foo(int (&arr)[N])
    (Not tested)
    typename should be std::size_t.

    Quote Originally Posted by Elysia
    Or you can do
    template<typename N>
    void foo(int arr[N])
    You would have to explicitly specify the template argument anyway, so you might as well pass a pointer argument instead.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,411
    Ah, error on my part. So it should be

    template<std::size_t N>
    void foo(int arr[N])

    template<std::size_t N>
    void foo(int (&arr)[N])

    It should not require having to specify N in this case. The compiler should be able to deduce that if arr is an int array passed to the function.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by Elysia
    It should not require having to specify N in this case. The compiler should be able to deduce that if arr is an int array passed to the function.
    Yeah, my comment about explicitly specifying the template argument was with respect to the one where the array would be converted to a pointer to its first element, since the N in the parameter is then not considered.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,411
    Ah, you may be right. I don't have a compiler to test right now >_<
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,017
    Quote Originally Posted by Elysia View Post
    Ah, you may be right. I don't have a compiler to test right now >_<
    codepad
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  9. #9
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    Thank you for all of the responses!

    However, when I tried to do this the simplest way that I could (simply making n equal to the size of the array I'm testing for), it still doesn't do anything.
    I've got it set up to make an array of random numbers between 1 and 99. Here's running it and printing the array before heapify:
    Code:
    ***** WELCOME TO LINELL'S HEAP OF STUFF! *****     
    Let me print the array of random numbers: 
    39
    35
    5
    2
    89
    48
    27
    66
    70
    61
    Now I'll run the heapify and this should change the order to reflect the array becoming a heap. However, all I get for output is the exact same array.

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    2,017
    What's your revised code?
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  11. #11
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    Here it is in its entirety:

    Code:
    /*
    
        Linell 
        Due on 11/11/11 <- I'm totally getting Skyrim
                   at 11:59 tonight.
     
    */
    #include <iostream>
    #include <cstdlib>
    #include <time.h>
    using namespace std;
    
        // The following functions will be used to make
        // and manipulate the heap.
    int parent(int);
    int left(int);
    int right(int);
    void heapify(int[], int);
    
    int main() {
        int daheap[100];
        
        cout << "***** WELCOME TO LINELL'S HEAP OF STUFF! *****";
        cout << "     Let me print the array of random numbers: ";
        srand(time(NULL));
        for (int i = 0; i < 10; i++) {
            daheap[i] = rand() % 100;
        }
        for (int i = 0; i < 10; i++) {
            cout << endl << daheap[i];
        }
        
        heapify(daheap, 0);
        
        cout << "\n\n\n     Alright, now for daheap sorted! :) ";
        for (int i = 0; i < 10; i++) {
            cout << endl << daheap[i];
        }
        
        getchar();
    }
    
        // Returns the parent of a certain node
    int parent(int i) {
        return (i/2);
    }
        // Returns the left child of a parent
    int left(int i) {
        return (2*i);
    }
        // Returns the right child of a parent
    int right(int i) {
        return (2*i+1);
    }
        // Heapifys an array
    void heapify(int array[], int i) {
        int largest = 0;
        int temp = 0;
        int n = 10;
        int l = left(i);
        int r = right(i);
        if (l <= n && array[l] > array[i]) {
            cout << "\n\nHERE IS THE DAMN PROBLEM";
            largest = l;
        }
        else {
            cout << "\n\nOkay, the else statement is working.";
            largest = i;
        }
        if (r <= n && array[i] > array[largest]) {
            cout << "\n\nOkay, largest = r.";
            largest = r;
        }
        if (largest != i) {
            cout << "\n\nAlright, this got down to the last step.";
            temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
            heapify(array, largest);
        }
    
    }

  12. #12
    Registered User
    Join Date
    Apr 2006
    Posts
    2,017
    Walk through what's supposed to happen in heapify when you call it with the parameters you do: i=0. It doesn't loop.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  13. #13
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    What should I pass through to it? I've tried passing a nine through, which should work, right? Same problem.

  14. #14
    Registered User
    Join Date
    Apr 2006
    Posts
    2,017
    You need to understand the algorithm. You don't have it quite right.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Heapify
    By Jamie32 in forum C++ Programming
    Replies: 0
    Last Post: 11-12-2003, 11:30 AM

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