Min-heap

This is a discussion on Min-heap within the C Programming forums, part of the General Programming Boards category; Hey guys, I'm having a doubt on min-heaps I thought you could help. I'm supposed to write a function that ...

  1. #1
    C Beginner
    Join Date
    Dec 2011
    Location
    Portugal
    Posts
    187

    Min-heap

    Hey guys, I'm having a doubt on min-heaps I thought you could help.

    I'm supposed to write a function that tests if a min-heap is well constructed, by other words, if all the sequences of numbers from the root till the last leaf are increasing.

    My struct is as following :

    Code:
    typedef struct minheap {
    int values[];
    int used;
    int size;
    } *MinHeap;
    Any help ?

    I thought about going from i=0 till i = used but that would only search one one way I think :/

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    If understood well,you want to check if the children of any parent have bigger values than him.You could use recursion. The root is the parent of the nodes that are the children of the root.Then every children becomes a parent which may have some children.Then these children are the parents for their children and so one

  3. #3
    C Beginner
    Join Date
    Dec 2011
    Location
    Portugal
    Posts
    187
    Yeah but I wanna do it for every single way from the root till the left leafs.
    How can I do it by recursion and how am I supposed to check his children (I have no way to do so).

    For example, my values array might be 1,4,6,9 when the children in the left is 6 and I wanna check that way but doing it recursively I would check 4 first correct ?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    It seems to me that it is quite easy to do this iteratively: for each node, check that its immediate children are less than or equal to itself.
    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
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    I think i have not understand something.What you want to do in the min-heap 1,4,6,9 is to go down from root like this :
    from 1 to 4,from 4 to 9 and then 9 is a leaf
    from 1 to 6 and then 6 is a leaf

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Quote Originally Posted by DeanWinchester View Post
    Yeah but I wanna do it for every single way from the root till the left leafs.
    Okay, recursion is perfect for that. Just stop trying to recurse down farther once you hit a NULL node (or the equivalent in your array-based version).
    How can I do it by recursion and how am I supposed to check his children (I have no way to do so).
    Do you know what recursion is in general? Can you, for example, write a recursive function to calculate terms of the Fibonacci sequence? Can you implement a basic binary search tree recursively? If not, either use an iterative approach or set the MinHeap aside and practice recursion.
    For example, my values array might be 1,4,6,9 when the children in the left is 6 and I wanna check that way but doing it recursively I would check 4 first correct ?
    You check whatever one you want first. If you want to only check the left child, do so. If only the right, check only the right. If you want to check right first, then left, do that. The choice is up to you.

    It looks like you're implementing this heap as an array without fully understanding the mechanics of the data structure. First, make sure you can implement a basic binary search tree using pointers and node allocation (i.e. not arrays). Then, figure out how to translate that to an array-based binary search tree.Once you understand that, it should be easy to translate the canonical heap implementation to an array based one.
    Last edited by anduril462; 08-28-2012 at 10:09 AM. Reason: removed stray quote tag

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by anduril462
    It looks like you're implementing this heap as an array without fully understanding the mechanics of the data structure. First, make sure you can implement a basic binary search tree using pointers and node allocation (i.e. not arrays). Then, figure out how to translate that to an array-based binary search tree.Once you understand that, it should be easy to translate the canonical heap implementation to an array based one.
    Err... the canonical heap implementation is an array based one, for both min-heap and max-heap.

    This is why I think that using recursion is very much unnecessary here: it is so simple to loop over the elements of the array and verify that each element and its children satisfy the min-heap property.
    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

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Since a heap is a complete binary tree (except possibly for the lowest elements), it is implemented as an array for efficency.

    To make sure we're on the same page, this

    1 2 3 4 5 6

    represents this:
    Code:
    .      1
        2     3
       4 5   6
    So, yeah, recursion is pointless for this.
    Code:
    int bad_heap = 0;
    for (i = 0; LEFT_CHILD(i) < size; i++)
        if (a[i] > a[LEFT_CHILD(i)] || a[i] > a[RIGHT_CHILD(i)]) { // use < for max heap
            bad_heap = 1;
            break;
        }
    As for "I have no way to check his children", I'm not sure what you mean by that. Didn't you learn about heaps? The children are easy to find; consider how to implement LEFT_CHILD and RIGHT_CHILD above.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    C Beginner
    Join Date
    Dec 2011
    Location
    Portugal
    Posts
    187
    Alright guys, thanks for all the replies.
    Iteratively it's so easy!

  10. #10
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Quote Originally Posted by laserlight View Post
    Err... the canonical heap implementation is an array based one, for both min-heap and max-heap.
    Interesting...I only recall learning the binary tree version.

    This is why I think that using recursion is very much unnecessary here: it is so simple to loop over the elements of the array and verify that each element and its children satisfy the min-heap property.
    Agreed, given his array implementation, iteration would be a better solution. My suggestion however was largely driven by the fact that he was visualizing the heap in a binary tree format, but couldn't figure out how to manipulate or access any of the elements in his array implementation. I think using a model that more closely matches what's in his head to figure out what to do first, then mapping/translating that to the array implementation would be beneficial. It's two smaller mental leaps rather than one large one.

    EDIT: Moot point I guess, he's got his answer
    Last edited by anduril462; 08-28-2012 at 10:11 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I think it's with the Heap...but is it...
    By Meganan in forum C++ Programming
    Replies: 9
    Last Post: 10-05-2005, 07:22 PM
  2. The heap
    By Frantic- in forum C++ Programming
    Replies: 2
    Last Post: 06-17-2005, 03:42 AM
  3. heap
    By m_adel in forum C Programming
    Replies: 8
    Last Post: 01-27-2005, 09:25 AM
  4. Anyone Know HEAP ?
    By Kam in forum C Programming
    Replies: 5
    Last Post: 09-14-2002, 07:47 AM
  5. heap
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-10-2001, 01:15 PM

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