Estructura de Datos
Se realizan pruebas de inserción y extracción de datos en un Heap. Primero se muestra el dato aleatorio a ingresar al heap, después el heap completo y por último la extracción ordenada de cada número del heap imprimiendo estado del heap en cada extracción.
Data Structure
Data insertion and extraction tests are performed in a Heap. First, the random data to be entered into the heap is shown, then the complete heap, and finally, the ordered extraction of each number from the heap, printing the heap status in each extraction.
main.cpp
#include <iostream>
#include "heap.hpp"
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 << "\n\n";
m.print();
cout << "\n\n";
for (int i = 0; i < 10; i++){
cout << "Extraer " << m.tout() << ": ";
m.print();
}
}
//https://dev.to/imnotleo/heap-39no
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-1));
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";
}
//https://dev.to/imnotleo/heap-39no
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);
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 */
//https://dev.to/imnotleo/heap-39no
Top comments (0)