
June 3rd, 2012, 09:15 AM
#1
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

June 3rd, 2012, 09:58 AM
#2
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.

June 3rd, 2012, 10:21 AM
#3
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.

June 3rd, 2012, 10:37 AM
#4
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.

June 3rd, 2012, 10:54 AM
#5
Re: Array to Heap Tree
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.

June 3rd, 2012, 11:25 AM
#6
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

June 3rd, 2012, 11:34 AM
#7
Re: Array to Heap Tree
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...
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.

June 3rd, 2012, 11:37 AM
#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?

June 3rd, 2012, 11:39 AM
#9
Re: Array to Heap Tree
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.

June 3rd, 2012, 11:43 AM
#10
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) ?

June 3rd, 2012, 11:48 AM
#11
Re: Array to Heap Tree
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 last1 into the heap defined by the range [first, last1)"?

June 3rd, 2012, 12:01 PM
#12
Re: Array to Heap Tree
Originally Posted by laserlight
Or, let me ask you: what do you understand by the statement that push_heap "inserts the element at the position last1 into the heap defined by the range [first, last1)"?
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?

June 3rd, 2012, 12:06 PM
#13
Re: Array to Heap Tree
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.
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?

June 3rd, 2012, 12:19 PM
#14
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)

June 3rd, 2012, 12:27 PM
#15
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;
}
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

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
