UsualStructure/Structure/自定义二叉堆模板.cpp

class tph_inc {
private:
	template<typename _T>
	static void swap(_T& a, _T& b) {
		_T t = a;
		a = b;
		b = t;
	}

	template<typename _T, typename _U>
	static void up(int at, int& siz, _T* heap, bool(*comp)(_U, _U)) {
		while (at > 1 && !((*comp)(heap[at >> 1], heap[at]))) {
			swap(heap[at >> 1], heap[at]);
			at >>= 1;
		}
	}

	template<typename _T, typename _U>
	static void down(int at, int& siz, _T* heap, bool(*comp)(_U, _U)) {
		while ((at << 1) <= siz) {
			int mson = at << 1;
			if (mson + 1 <= siz && (*comp)(heap[mson + 1], heap[mson]))
				mson++;
			if ((*comp)(heap[at], heap[mson]))
				break;
			swap(heap[at], heap[mson]);
			at = mson;
		}
	}
public:
	template<typename _T, typename _U>
	static void ins(_T x, int& siz, _T* heap, bool(*comp)(_U, _U)) {
		heap[++siz] = x;
		up(siz, siz, heap, comp);
	}

	template<typename _T, typename _U>
	static void del(int at, int& siz, _T* heap, bool(*comp)(_U, _U)) {
		swap(heap[at], heap[siz]);
		heap[siz--] = 0;
		if ((!((*comp)(heap[at >> 1], heap[at]))))
			up(at, siz, heap, comp);
		else
			down(at, siz, heap, comp);
	}
};