/ Codes

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_;
};

LengErrong

ss://Y2hhY2hhMjAtaWV0Zi1wb2x5MTMwNTpqZXN1c2lzbG92ZUAzNS4yMDIuMjM4LjI0Ojg5MTE#Outline

Read More