**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 4 Years Ago by R1111

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.

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?

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.

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?

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 4 Years Ago by deceptikon

This article has been dead for over six months. Start a new discussion instead.