大根堆小根堆

偷学的罒ω罒，非常好用的模版，分享一下。学过堆排应该很容易就看懂了，看不懂学一下堆排，不好懂的地方我也写了注释

小根堆

template<typename T>
class smallest_heap {
private:
	//建堆
	T heap[10001];
	int len;
public:
	smallest_heap();
	void push(T const&);
	void pop();
	T top();
	int size();
	bool empty();
};
template<typename T>
smallest_heap<T>::smallest_heap() {
	len = 0;
	memset(heap, 0, sizeof(heap));
}
template<typename T>
void smallest_heap<T>::push(T const& n) {
	//将元素添加到堆尾
	heap[++len] = n;
	int son = len, father = son / 2;
	//由于是建立小根堆，当子节点小于父节点时，且父节点要大于等于最小下标
	while (heap[son] < heap[father] && father >= 1) {
		//交换
		std::swap(heap[son], heap[father]);
		//不断往上交换
		son = father, father = son / 2;
	}
}
//删除堆顶元素
template<typename T>
void smallest_heap<T>::pop() {
	//交换首元素和尾元素
	std::swap(heap[1], heap[len]);
	//将最后一个元素置0
	heap[len--] = 0;
	int father = 1, son = 2;
	//当子元素下标不超过最后一个
	while (son <= len) {
		//这一行用于找到当前节点的左右孩子中值较小的那一个，将其索引赋给 son。
		if (son<len && heap[son]>heap[son + 1])son++;
		//有序堆，只需要找到一个heap[son]>heap[father]的节点，否则就往上交换
		if (heap[father] > heap[son]) {
			std::swap(heap[father], heap[son]);
			father = son, son = father * 2;
		}
		else break;
	}
}
template<typename T>
T smallest_heap<T>::top() {
	return heap[1];
}
template<typename T>
int smallest_heap<T>::size() {
	return len;
}

template<typename T>
bool smallest_heap<T>::empty() {
	return len;
}

很容易找到堆里的最小元素。

大根堆，改三个大于小于号就好了

template<typename T>
class smallest_heap {
private:
	//建堆
	T heap[10001];
	int len;
public:
	smallest_heap();
	void push(T const&);
	void pop();
	T top();
	int size();
	bool empty();
};
template<typename T>
smallest_heap<T>::smallest_heap() {
	len = 0;
	memset(heap, 0, sizeof(heap));
}
template<typename T>
void smallest_heap<T>::push(T const& n) {
	heap[++len] = n;
	int son = len, father = son / 2;
	//1.大根堆改这里<改成>
	while (heap[son] > heap[father] && father >= 1) {
		//交换
		std::swap(heap[son], heap[father]);
		//不断往上交换
		son = father, father = son / 2;
	}
}
//删除堆顶元素
template<typename T>
void smallest_heap<T>::pop() {
	//交换首元素和尾元素
	std::swap(heap[1], heap[len]);
	//将最后一个元素置0
	heap[len--] = 0;
	int father = 1, son = 2;
	//当子元素下标不超过最后一个
	while (son <= len) {
		//大根堆改这，>改成<
		if (son<len && heap[son]<heap[son + 1])son++;
        //这里同理
		if (heap[father] < heap[son]) {
			std::swap(heap[father], heap[son]);
			father = son, son = father * 2;
		}
		else break;
	}
}
template<typename T>
T smallest_heap<T>::top() {
	return heap[1];
}
template<typename T>
int smallest_heap<T>::size() {
	return len;
}

template<typename T>
bool smallest_heap<T>::empty() {
	return len;
}