Heap

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