main.cpp
#include <iostream>
#include "heap.hpp"
int main() {
srand(time(NULL));
int n;
char c;
cin >> n >> c;
if (c == 'h' || c == 'H') {
int *a = new int [n];
for (int i = 0; i < n; i++){
int x = rand() % (10*n) + 1;
a[i] = x;
}
cout << "Array: \n";
cout << "[ ";
for (int i = 0; i < n; i++) cout << a[i] <<" ";
cout << "]\n";
heap m(n);
for (int i = 0; i < n; i++){
m.ins(a[i]);
}
cout << "Heapsorted array: \n";
m.hSort();
m.print();
} else if (c == 'q' || c == 'Q') {
cout << "Prueba de Q";
} else if (c == 'm' || c == 'M') {
cout << "Prueba de M";
}
return 0;
}
heap.cpp
#include "heap.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[maxChild(i)]){
int m = maxChild(i);
int c = a[i];
a[i] = a[m];
a[m] = c;
i = m;
}
return x;
}
int heap::maxChild(int i) {
assert(i < parent(s));
if (right(i) > s) 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";
}
void heap::hSort() {
int k = s;
while (k > 0) {
swap(a[0], a[--k]);
int i = 0;
while ( i < parent(k) and a[i] < a[maxChild(i)] ) {
int m = maxChild(i);
swap(a[i], a[m]);
i = m;
}
}
}
heap.hpp
#ifndef heap_hpp
#define heap_hpp
#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 maxChild(int);
void hSort();
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 */
Top comments (0)