---
description: >-
  Topic # Binary Heap (detail) - Array that is sorted in decreasing order a
  max-oriented heap.
---

# Maximum-Oriented PQ using Binary Heap

```cpp
#include <iostream>
using namespace std;

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

     bool less(const key, const key);

     // ! Swim & sink are heap helper functions
     // Promotion: child's key becomes a larger key than its parent's key
     void swim(int);

     // Demotion: Parent's key becomes smaller than one (or both) of its children's
     void sink(int);

     bool isEmpty();

public:
     MaxPQ(int);

     MaxPQ(const MaxPQ<key> &);

     bool isFull();

     // At most 1 + lg N compares
     void insert(const key);

     // At most 2 lg N compares
     key delMax();

     void print();
};

template <typename key>
MaxPQ<key>::MaxPQ(const MaxPQ<key> &obj)
{
     this->N = obj.N;
     this->arr = new key[obj.N];
     this->i = obj.i;
     for (int j = 1; j <= i; j++)
          this->arr[j] = obj.arr[j];
}

template <typename key>
MaxPQ<key>::MaxPQ(int capacity)
{
     N = capacity + 1;
     arr = new key[capacity + 1]{NULL};
}

template <typename key>
void MaxPQ<key>::print()
{
     cout << endl;
     for (int j = 1; j <= i; j++)
          cout << arr[j] << " ";
     cout << endl;
}

template <typename key>
bool MaxPQ<key>::isFull()
{
     return i == N - 1;
}

template <typename key>
bool MaxPQ<key>::isEmpty()
{
     return i == 0;
}

template <typename key>
bool MaxPQ<key>::less(const key key1, const key key2)
{
     return key1 < key2;
}

template <typename key>
void MaxPQ<key>::swim(int k)
{
     while (k > 1 && less(arr[k / 2], arr[k]))
     {
          swap(arr[k], arr[k / 2]);
          k = k / 2;
     }
}

template <typename key>
void MaxPQ<key>::sink(int k)
{
     while (2 * k <= i)
     {
          int j = 2 * k;

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

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

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

template <typename key>
void MaxPQ<key>::insert(const key val)
{
     arr[++i] = val;
     swim(i);
}

template <typename key>
key MaxPQ<key>::delMax()
{
     if (isEmpty())
          return -1;
     key max = arr[1];
     swap(arr[1], arr[i--]);
     sink(1);
     arr[i + 1] = NULL; // prevent loitering
     return max;
}

int main()
{
     MaxPQ<int> pq(6);
     while (!pq.isFull())
     {
          int key;
          cin >> key;
          pq.insert(key);
     }
     pq.print();

     MaxPQ<int> pq2(pq); // calling copy Construstor

     cout << "Max Node: " << pq.delMax()<<endl;
     cout << "Max Node: " << pq.delMax()<<endl;
     pq.print();

     cout << "--PQ2--";
     pq2.print();
}
```

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2Frcc5BjytAPuwM4Uaods3%2Fimage.png?alt=media&#x26;token=d1109b89-44dc-4e4f-855a-8eca4cc0854e" alt=""><figcaption></figcaption></figure>

