#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cassert>
    #include<string>
    #include<cmath>
    #include<iostream>
    #include<cmath>
    #include<sstream>
    #include<stdio.h>
    #include<stdlib.h>
     using namespace std;

  int const N = 20; // or whatever

  void swap(int&i, int&j)
   {
    int temp = i;
    i = j;
    j = temp;
   }

  struct heap
   {
    int item[N];
    int size = 0; // intially empty
   };

  int parent(int i)
   {
    assert(i > 1);
    return i/2;
   }

  int lchild(int i)
   {
    return 2*i;
   }

  int rchild(int i)
   {
    return 2*i+1;
   }

  void bubbleup(heap&h,int i)
   {
    if(i > 1)
     {
      int p = parent(i);
      if(h.item[i] < h.item[p])
       {
        swap(h.item[i],h.item[p]);
	bubbleup(h,p);
       }
     }
   }

  void bubbledown(heap&h,int i)
   {
    int lc = lchild(i);
    int rc = rchild(i);
    if(lc == h.size)
     if(h.item[lc] < h.item[i])
      swap(h.item[lc],h.item[i]);
     else;
    else if(lc < h.size)
     {
      int mc;
      if(h.item[lc] < h.item[rc]) mc = lc;
      else mc = rc;
      if(h.item[mc] < h.item[i])
       {
        swap(h.item[mc],h.item[i]);
	bubbledown(h,mc);
       }
     }
   }

  void insert(heap&h,int newitem)
   {
    h.size++;
    h.item[h.size] = newitem;
    bubbleup(h,h.size);
   }

  bool empty(heap&h)
   {
    return (h.size == 0);
   }

  int deletemin(heap&h)
   {
    int rslt = h.item[1];
    h.item[1] = h.item[h.size];
    h.size--;
    bubbledown(h,1);
    return rslt;
   }

  void traverse(heap&h)
   {
    for(int i = 1; i <= h.size; i++)
     cout << h.item[i];
    cout << endl;
   }

  void message()
   {
    cout << "This program implements a min-heap, implemented as an almost ";
    cout << "complete binary" << endl;
    cout << "tree, which in turn is implemented";
    cout << "as an array, ";
    cout << "as we saw in class.  After " << endl;
    cout << "initialization as an empty heap, the ";
    cout << "sequence 2, 7, 0, 9, 3, 1, 5, 6, 8, 4 " << endl;
    cout << "is inserted. ";
    cout << "Then, deletemin is executed until the heap is empty." << endl;
   }

  int main()
   {
    message();
    heap h;
    traverse(h);
    insert(h,2);
    traverse(h);
    insert(h,7);
    traverse(h);
    insert(h,0);
    traverse(h);
    insert(h,9);
    traverse(h);
    insert(h,3);
    traverse(h);
    insert(h,1);
    traverse(h);
    insert(h,5);
    traverse(h);
    insert(h,6);
    traverse(h);
    insert(h,8);
    traverse(h);
    insert(h,4);
    traverse(h);
    cout << endl;
    traverse(h);
    while(not empty(h))
     {
      deletemin(h);
      traverse(h);
     }
    cout << endl;
    return 1;
   }