Array to Heap Tree

[R1111]

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:

#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

[laserlight]

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.

[ahoodin]

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

[R1111]

Thank you laserlight and ahoodin,

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

 #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.

[laserlight]

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.

[R1111]

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

[laserlight]

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...

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.)

[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?

[laserlight]

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.

[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) ?

[laserlight]

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)"?

[R1111]

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?

    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?

[laserlight]

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.

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?

[R1111]

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.

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)

[laserlight]

Something like this:

#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;
}