Array with Make Heap

[R00]

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 will be appreciated :D

[R00]

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?

[budman85]

The iterators are passing the beginning and end of a vector.


Check out the reference for more help:

http://www.cplusplus.com/reference/algorithm/make_heap/

[sqrt3]

if the array like this:
int ia[3]={1,2,3};
so,the vector like this.

vector <int > val(ia,ia+sizeof(ia)/sizeof(int));

//SO:begin=ia,end=ia+sizeof(ia)/sizeof(int);

[R00]

thanks guys,
I've modified my code like

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

and would like to know how to use pop_heap and push_heap to add/remove elements to/from the array.

@sqrt3 I'm not using vectors (i'm not familiar with them)
@budman85 the reference uses "template" which I'm not familiar with either :/

[budman85]

In order to push and pop on the heap array,
you would need to use a dynamic array
otherwise, you max out quick with a fixed length array.

Vectors handle this much more efficiently, and are worth getting to know.
They are easy to learn.

When it comes to iterators, standard pointers can be passed.

Here is an example of using arrays ( following the example for make_heap)

// range heap example
#include <iostream>
#include <algorithm>


using namespace std;

const int MAX_SIZE = 10;
int max_array = MAX_SIZE;
int array_size;

int * heap_push(int *numbers, int value)
{
    if ( array_size + 1 >= max_array )
    {
        max_array += MAX_SIZE;
        int *temp = new int[max_array];
        for (int i=0; i<array_size; i++)
            temp[i] = numbers[i];
        delete [] numbers;
        numbers = temp;
    }
    numbers[array_size] = value;
    array_size++;
    return numbers;
}

int heap_pop(int *numbers)
{
   array_size--;
   int value = numbers[array_size];
   numbers[array_size] = 0;
   return value;
}

int main ()
{
    int myints[] = {10,20,30,5,15,24,78,54,22,31,33,65,12};
    int myints_size = sizeof(myints) / sizeof(int);

    int *numbers = new int[max_array];
    array_size = 0;

    for (int i=0; i<myints_size; i++)
        numbers = heap_push(numbers, myints[i]);

    cout << endl << "original" << endl;
    for (int i=0; i<array_size; i++)
        cout << i << " " << numbers[i] << endl;


    make_heap(&numbers[0],&numbers[array_size]);

    cout << "\ninitial heap " << numbers[0] << endl;

    pop_heap (&numbers[0],&numbers[array_size]);
    int x = heap_pop(numbers);
    cout << "after pop " << numbers[0] << endl;

    heap_push(numbers, 99);
    make_heap(&numbers[0],&numbers[array_size]);
    cout << "after push " << numbers[0] << endl;

    sort_heap(&numbers[0],&numbers[array_size]);

    cout << endl << "sorted" << endl;
    for (int i=0; i<array_size; i++)
        cout << i << " " << numbers[i] << endl;

    cout << endl;

    delete [] numbers;

    return 0;
}

original
0 10
1 20
2 30
3 5
4 15
5 24
6 78
7 54
8 22
9 31
10 33
11 65
12 12

initial heap 78
after pop 65
after push 99

sorted
0 5
1 10
2 12
3 15
4 20
5 22
6 24
7 30
8 31
9 33
10 54
11 65
12 99

Edit: fixed a bug :)