CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17
  1. #1
    Join Date
    Jun 2012
    Posts
    8

    Exclamation Array to Heap Tree

    Hello,

    If I have an array, and want to make a heap tree out of it using make heap and sort heap, how would I do it? I'm struggling because I didn't take any course in data structure.

    I tried googling stuff and I got to the following:
    Code:
    #include <algorithm> // for std::make_heap, std::sort_heap
     
    template <typename Iterator>
    void heap_sort(Iterator begin, Iterator end)
    {
        std::make_heap(begin, end);
        std::sort_heap(begin, end);
    }

    The thing is, I don't know what's the "Iterator" doing exactly and what's begin/end, how can I use arrays with the former piece of code?


    Any help -in c++- will be appreciated

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Array to Heap Tree

    You would only need to use make_heap, methinks. The begin/end iterators of an array would be a pointer to the first element of the array and a pointer to one past the last element of the array, respectively.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Mar 2001
    Posts
    2,529

    Re: Array to Heap Tree

    An Iterator is like a pointer to an array element. To iterate is to step through to the next element in the array. MyIterator++ would iterate to the next element. A heap is a binary tree that is in order from highest priority (or value) to least. The priority Queue is implemented as a heap, where you pop the highest priority or value item off the top of a heap, and then reorder the remaining elements into another heap. Note there are a few more rules to priority queue than that, but hope it gives you some more hints about your heap.



    The thing is, I don't know what's the "Iterator" doing exactly and what's begin/end, how can I use arrays with the former piece of code?


    Any help -in c++- will be appreciated
    ahoodin
    To keep the plot moving, that's why.

  4. #4
    Join Date
    Jun 2012
    Posts
    8

    Lightbulb Re: Array to Heap Tree

    Thank you laserlight and ahoodin,

    now I've used make_heap and sort_heap, like this:

    Code:
     #include <iostream>
        #include <algorithm>
        void heap_sort(int* begin, int* end)
        {
        std::make_heap(begin, end);
        std::sort_heap(begin, end);
        }
        int main ()
        {
        int a[ ] = {1, 2, 3, 4, 5, 6, 7};
        const int n = 7;
        heap_sort( &a[0], &a[n]);
        return 0;
        }

    how can I use pop_heap and push_heap in the same manner with the same array without using template stuff.

  5. #5
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Array to Heap Tree

    Quote Originally Posted by R1111
    how can I use pop_heap and push_heap in the same manner with the same array without using template stuff.
    What is the bigger picture of what you are trying to do?

    Do you understand what pop_heap and push_heap do? If not, read stuff like cppreference.com's entries on pop_heap and push_heap.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  6. #6
    Join Date
    Jun 2012
    Posts
    8

    Re: Array to Heap Tree

    I want to add values to my array, push_heap should do it, I don't know how to use it. The example on the reference page uses vectors and "auto." Do you know what to do/how to use push_heap in a simple clean code like the above?

    thanks

  7. #7
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Array to Heap Tree

    Quote Originally Posted by R1111
    I want to add values to my array, push_heap should do it, I don't know how to use it.
    You cannot add values to your array because your array's size is fixed at compile time. What you can do is create an array as large as you will ever need and then just use part of it incrementally, but...

    Quote Originally Posted by R1111
    The example on the reference page uses vectors and "auto." Do you know what to do/how to use push_heap in a simple clean code like the above?
    Using a vector would be appropriate. You don't need to use auto here (it was merely used as a convenience, as intended, in printing the vector's contents).

    Besides, do you understand what the example does? If you understand, you can apply it to an array. If you don't understand... what exactly don't you understand? (That is, I can spoonfeed you code, but if you don't understand it, then it is a pointless exercise.)
    Last edited by laserlight; June 3rd, 2012 at 11:36 AM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  8. #8
    Join Date
    Jun 2012
    Posts
    8

    Re: Array to Heap Tree

    well, it's confusing, there's this "v.push_back(value)" with vectors, but what's the equivalent if I'm using an array instead of a vector?

  9. #9
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Array to Heap Tree

    Quote Originally Posted by R1111
    well, it's confusing, there's this "v.push_back(value)" with vectors, but what's the equivalent if I'm using an array instead of a vector? .
    There is no equivalent. You cannot increase the size of an array. As I mentioned, you could create an array as big as you will ever need then incrementally use it, but unless you have special and convincing reasons to avoid std::vector, it is simpler to just use std::vector.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  10. #10
    Join Date
    Jun 2012
    Posts
    8

    Re: Array to Heap Tree

    Assuming that I defined a bigger array, and only a few values are associated with the first few slots. How can I add values using push_heap, if there's no equivalent to v.push_back(value) ?

  11. #11
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Array to Heap Tree

    Quote Originally Posted by R1111
    Assuming that I defined a bigger array, and only a few values are associated with the first few slots. How can I add values using push_heap, if there's no equivalent to v.push_back(value) ?
    Simple: you pass a pointer to one past the newest array element in use as the second argument to push_heap.

    Or, let me ask you: what do you understand by the statement that push_heap "inserts the element at the position last-1 into the heap defined by the range [first, last-1)"?
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  12. #12
    Join Date
    Jun 2012
    Posts
    8

    Re: Array to Heap Tree

    Quote Originally Posted by laserlight View Post
    Or, let me ask you: what do you understand by the statement that push_heap "inserts the element at the position last-1 into the heap defined by the range [first, last-1)"?
    It inserts the value to the left of the last level leaf?

    Simple: you pass a pointer to one past the newest array element in use as the second argument to push_heap.
    so would it be something like this?

    Code:
        void add_value (double* begin, double* end)
        {
    	push_heap(begin, end);
    	}
    
        int main ()
        {
        int a[ ] = {1, 2, 3, 4, 5, 6, 7};
        const int n = 11;
        add_value( &a [0],  &a [n]);
        return 0;
        }
    but where do I put the value that I want to add? let's say I want to add number 50?

  13. #13
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Array to Heap Tree

    Quote Originally Posted by R1111
    It inserts the value to the left of the last level leaf?
    No, that is not what it means. Rather, it states that the element at that position in the range (i.e., the range of the array, vector, etc) is inserted into the heap that consists of the elements of the range.

    Quote Originally Posted by R1111
    so would it be something like this?
    No, because your array has a size of 7, and all 7 elements of the array are in use. Furthermore, push_heap only works if the rest of the range is a heap. For this scheme to work, you need to keep track of the number of elements in use. What's stopping you from using a std::vector?
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  14. #14
    Join Date
    Jun 2012
    Posts
    8

    Re: Array to Heap Tree

    I don't know how to deal with vectors, first encounter! I'm trying to use what I'm somewhat familiar with. I'll try to learn vectors soon.

    But now I still don't get how I'll get push_heap to work :S


    I see how I have the array fixed with 7 entries, I changed that now.

    Code:
    void add_value (double* begin, double* end)
        {
    	push_heap(begin, end);
    	}
    
        int main ()
        {
         const int n = 11;
        int a[n] = {1, 2, 3, 4, 5, 6, 7};
        
        add_value( &a [0],  &a [n]);
        return 0;
        }
    agh sorry if I'm kinda slow, but how would I add the number "50" to the heap tree. (assuming I have the previous structure of heap tree already there and sorted)

  15. #15
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Array to Heap Tree

    Something like this:
    Code:
    #include <algorithm>
    
    int main()
    {
        const int capacity = 11;
        int a[capacity] = {1, 2, 3, 4, 5, 6, 7};
        int size = 7;
        std::make_heap(a, a + size);
    
        // Add 50 to the heap:
        a[size++] = 50;
        std::push_heap(a, a + size);
    
        return 0;
    }
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

Page 1 of 2 12 LastLast

Tags for this Thread

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured