Heap Tree - Array

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

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

[deceptikon]

This page has a good explanation with several different code variations. Read through that and if you have any specific questions, I'll be happy to answer them for you.

[R1111]

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]

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]

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]

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.

[R1111]

I see! Thanks a lot :D