c++: Max Heap Template

https://en.wikipedia.org/wiki/Min-max_heap
My simple implementation of max heap.
Change the compare from > to < in below codes, you will get a min heap.

template<typename T>
class MaxHeap {
public:
 MaxHeap() {
  size_ = 0;
  capacity_ = 2;
  heap_ = new T[capacity_];
 }
 MaxHeap(int capacity) {
  if (capacity >= 2) {
   heap_ = new T[capacity];
   capacity_ = capacity;
   size_ = 0;
  }
  else {
   size_ = 0;
   capacity_ = 2;
   heap_ = new T[capacity_];
  }
 }
 ~MaxHeap() {
  if (heap_)
   delete[] heap_;
 }
public:
 int size() { return size_; }
 void insert(const T& t) {
  if ((size_+1) >= capacity_) {
   capacity_ *= 2;
   T* tmp = new T[capacity_];
   for (int i = 0; i <= size_; i++)
    tmp[i] = heap_[i];
   delete[] heap_;
   heap_ = tmp;
  }
  size_++;
  heap_[size_] = t;
  int i = size_;
  int tmp = heap_[i];
  while (i > 1 && tmp > heap_[i / 2]) {
   heap_[i] = heap_[i / 2];
   heap_[i / 2] = tmp;
   tmp = heap_[i / 2];
   i /= 2;
  }
  heap_[i] = tmp;
 }
 T max() {
  return heap_[1];
 }
 int index(const T& t) {
  return index(1, t);
 }
 void removeByIndex(int i) {
  if (i < 1)
   return;
  if (heap_[size_] == heap_[i]) {
   heap_[i] = heap_[size_];
   size_--;
   return;
  }
  if (heap_[size_] < heap_[i]) {
   heap_[i] = heap_[size_];
   size_--;
   maxDown(i);
   return;
  }
  heap_[i] = heap_[size_];
  size_--;
  maxUp(i);
 }
 void remove(const T& t) {
  return removeByIndex(index(t));
 }
private:
 inline int index(int i, const T& t) {
  if (heap_[i] < t)
   return -1;
  if (heap_[i] == t)
   return i;
  int r = index(2 * i, t);
  if (r != -1)
   return r;
  return index(2 * i + 1, t);
 }
 inline void maxDown(int i) {
  if (i * 2 > size_ && (i * 2 + 1) > size_)
   return;
  int l = i * 2;
  int r = l + 1;
  int m = l;
  if (r <= size_ && heap_[r] > heap_[l])
   m = r;
  if (heap_[m] <= heap_[i])
   return;
  T tmp = heap_[i];
  heap_[i] = heap_[m];
  heap_[m] = tmp;
  maxDown(m);
 }
 inline void maxUp(int i) {
  if (i <= 1)
   return;
  int p = i / 2;
  if (heap_[p] >= heap_[i])
   return;
  T tmp = heap_[i];
  heap_[i] = heap_[p];
  heap_[p] = tmp;
  maxUp(p);
 }
private:
 T* heap_;
 int capacity_;
 int size_;
};

static MaxHeap<int>* all[101] = { 0, };
static int mt = 0;

void Init()
{
 for (int i = 1; i < mt; i++)
  if (all[i]) {
   delete all[i];
   all[i] = 0;
  }
 mt = 0;
}

void insertID(int ProductType, int ProductID)
{
 if (!all[ProductType])
  all[ProductType] = new MaxHeap <int>(50001) ;
 all[ProductType]->insert(ProductID);
 if ((ProductType + 1) > mt)
  mt = ProductType + 1;
}

int highestID(int ProductType)
{
 if (!all[ProductType] || all[ProductType]->size() <= 0)
  return -1;
 return all[ProductType]->max();
}

int findhighestID(int type)
{
 int maxType = -1;
 int maxId = -1;
 for (int i = 1; i < mt; i++)
  if (all[i] && all[i]->size() > 0) {
   int max = all[i]->max();
   if (max > maxId) {
    maxId = max;
    maxType = i;
   }
  }
 if (type == 0)
  return maxType;
 return maxId;
}

void demarket(int ProductID)
{
 for (int i = 1; i < mt; i++)
  if (all[i]) {
   int index = all[i]->index(ProductID);
   if (index >= 1) {
    all[i]->removeByIndex(index);
    break;
   }
  }
}

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️