simply implement min heap, there's a faster version in repo "boring", but not very conveniant when prototyping

mheap.h

/**
 * Implement a min binary heap class for scalar type.
 */

#ifndef MHEAP_H
#define MHEAP_H

#include <vector>
#include <assert.h>

template<typename DT>
struct MHeap {
        DT *data;
        int size, cap;
        
        explicit
        MHeap(unsigned int sz) {
                assert(sz > 0);
                data = new DT[sz];
                cap = sz;
                size = 0;
        }

        ~MHeap() {
                delete []data;
                size = cap = 0;
        }

        void
        insert(DT v) {
                if (size < cap) {
                        data[size++] = v;
                        bubble_up(size-1);
                }
                else if (v > data[0]) {
                        data[0] = v;
                        bubble_down(0);
                }
        }

private:
        inline int
        parent(int i) {
                return i == 0 ? -1 : (i-1)/2;
        }

        inline int
        lchild(int i) {
                return i*2+1;
        }
        
        inline void
        bubble_up(int i) {
                int p = parent(i);
                if (p >= 0 && data[p] > data[i]) {
                        DT t = data[p];
                        data[p] = data[i];
                        data[i] = t;
                        bubble_up(p);
                }
        }

        inline void
        bubble_down(int i) {
                int lc = lchild(i);
                int min_i = i;
                DT t = data[i];
                
                if (lc < size && data[lc] < t) {
                        min_i = lc;
                        t = data[lc];
                }

                if (lc+1 < size && data[lc+1] < t) {
                        min_i = lc+1;
                }

                if (min_i != i) {
                        t = data[i];
                        data[i] = data[min_i];
                        data[min_i] = t;
                        bubble_down(min_i);
                }
        }
};

#endif