heap minchild

#include <stdio.h>
#include <iostream>
#include <cassert>
using namespace std;

class heap {

int parent(int i) { return (i – 1) / 2; }
int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }

int n; // capacidad
int s; // tamaño

int *a; // arreglo

public:

heap(int);
~heap();

void ins(int);
int tout();
int minChild(int);

int capacity() const { return n; }
int size() const { return s; }

bool empty() const { return s == 0; }
bool full() const { return s == n; }

void print();
};

#endif /* stack_hpp */

heap::heap(int c){

n = c;
s = 0;

a = new int[n];
}

heap::~heap(){

delete[] a;
}

void heap::ins(int x){

assert(!full());

a[s] = x;
int i = s++;
while (i > 0 && a[i] > a[parent(i)]) {
int c = a[i];
a[i] = a[parent(i)];
a[parent(i)] = c;

i = parent(i);
}

}

int heap::tout(){
assert(!empty());

int x = a[0];
int i = 0;
a[0] = a[–s];
while (i <= parent(s-1) && a[i] > a[minChild(i)]){

int m = minChild(i);
int c = a[i];
a[i] = a[m];
a[m] = c;
i = m;
}

return x;
}

int heap::minChild(int i) {

assert(i <= parent(s-1));

if (right(i) > s-1) return left(i);
if (a[left(i)] > a[right(i)]) { return left(i); }
else return right(i);

}

void heap::print(){

cout << “[ “;
for (int i = 0; i < s; i++) cout << a[i] <<” “;
cout << “]n”;
}

int main() {

srand((unsigned) time(nullptr));

int n = 100;

heap m(n);

for (int i = 0; i < 10; i++){

int x = rand() % n + 1;

cout << “Agregar ” << x << “: “;

m.ins(x);
m.print();
}

cout << “nn”;
m.print();
cout << “nn”;
for (int i = 0; i < 10; i++){

cout << “Extraer ” << m.tout() << “: “;

m.print();
}

}