Minimum-Oriented PQ using Binary Heap

Topic # Binary Heap (detail)

#include <iostream>
using namespace std;

template <typename key>
class MinPQ
{
     key *arr;
     int N;
     int i = 0;

     bool greeter(key key1, key key2)
     {
          return key1 > key2;
     }
     // ! swim & sink are heap helper functions

     // Promotion: Child's key becomes smaller key than its parent's key
     void swim(int k)
     {
          while (k > 1 && greeter(arr[k / 2], arr[k]))
          {
               swap(arr[k], arr[k / 2]);
               k = k / 2;
          }
     }
     // Demotion: Parent's key becomes Bigger than one (or both) of its children's
     void sink(int k)
     {
          while (2 * k <= i)
          {
               int j = 2 * k;

               if (j < i && greeter(arr[j], arr[j + 1]))
                    j++; // find out which one is smaller 2k or 2k+1

               if (!greeter(arr[k], arr[j]))
                    break; // break if the parent's key is smaller than both children's key

               swap(arr[k], arr[j]);
               k = j; // moving down the heap
          }
     }

     bool isEmpty()
     {
          return i == 0;
     }

public:
     MinPQ(int capacity) : N(capacity + 1)
     {
          arr = new key[capacity + 1]{NULL};
     }

     bool isFull()
     {
          return i == N - 1;
     }

     // At most 1 + lg N compares
     void insert(key val)
     {
          arr[++i] = val;
          swim(i);
     }

     // At most 2 lg N compares
     key delMin()
     {
          if (isEmpty())
               return -1;
          key min = arr[1];
          swap(arr[1], arr[i--]);
          sink(1);
          arr[i + 1] = NULL; // prevent loitering
          return min;
     }

     void print()
     {
          cout << endl;
          for (int j = 1; j <= i; j++)
               cout << arr[j] << " ";
          cout << endl;
     }
};

int main()
{
     MinPQ<int> *bt = new MinPQ<int>(6);
     while (!bt->isFull())
     {
          int key;
          cin >> key;
          bt->insert(key);
     }
     bt->print();
     cout << "Max Node: " << bt->delMin();
     bt->print();
}