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

Any help -in c++- will be appreciated :D**

R1111
0
Newbie Poster

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

Any help -in c++- will be appreciated :D**

Edited
by R1111

Jump to PostThe 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?

"Iterator" in this case is a generic term for the location of the first item in the collection and one past the last …

Jump to PostAha! so is it completely fine to drop "iterator" and template <typename Iterator> ?

Yes, but only if you replace any use of Iterator with the appropriate corresponding type. In your example, int isn't the correct type; it would be int* because that's the correct "iterator" type for …

deceptikon
1,790
Code Sniper
Team Colleague
Featured Poster

R1111
0
Newbie Poster

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?

deceptikon
1,790
Code Sniper
Team Colleague
Featured Poster

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?

"Iterator" in this case is a generic term for the location of the first item in the collection and one past the last item in the collection. You can translate it directly to arrays like so:

```
int a[] = {1, 2, 3, 4, 5, 6, 7};
const int n = 7;
heap_sort(&a[0], &a[n]);
```

`&a[0]`

is the address of the first item, and because arrays are indexed 0 to n-1, `&a[n]`

is the address of one past the last valid item. Note that this is perfectly valid. The C++ standard explicitly allows you to take the address of one past the last valid index, and as long as you don't try to read the valid there, it's completely safe.

R1111
0
Newbie Poster

Aha! so is it completely fine to drop "iterator" and template <typename Iterator> ?

and write the code as:

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

without reference to the address? or do I have to reference the address?

deceptikon
1,790
Code Sniper
Team Colleague
Featured Poster

Aha! so is it completely fine to drop "iterator" and template <typename Iterator> ?

Yes, but only if you replace any use of Iterator with the appropriate corresponding type. In your example, int isn't the correct type; it would be int* because that's the correct "iterator" type for an array of int. It's important to recognize that the template parameter is just a fancy cut and paste. It figures out what type you're actually using and replaces the template with a concrete definition using that type. Note that we're working with addresses here, not data values, so the correct conversion (and what the template system would do automagically) results in 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;
}
```

You *must* have a valid iterator, even if the concrete form of the iterator is a pointer, because that's just how make_heap() and sort_heap() are written. If you're writing your own heap sort algorithm you can do what you want and make it work by passing two indices, but when using a library you have no choice but to conform to its design.

Edited
by deceptikon

R1111
0
Newbie Poster

I see! Thanks a lot :D

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.