1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
|
// 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;
}
|