[数据结构与算法]精巧的堆（优先队列）

1、思维导图

2、实现代码

#include <iostream>
#include<vector>
using namespace std;
//着重接口的思想
template<typename T>
class BinaryHeap {
public:
	BinaryHeap(const vector<T>& items);
	T& findmin() const;
	void insert(T& x);
	void deleteMin();

private:
	int currentSize;//记录堆中的元素个数
	vector<T> array;//堆数组
	void buildHeap();
	void percolateDown(int hole);
};


template<typename T>
BinaryHeap<T>::BinaryHeap(const vector<T>& items):currentSize(items.size()),array(items.size()+10) {
	for (int i = 0; i < items.size(); ++i) {
		array[i + 1] = items[i];		
	}
	buildHeap();
}
template<typename T>
T& BinaryHeap<T>::findmin() const {
	return array[1];
}
template<typename T>
void BinaryHeap<T>::insert(T& x) {
	if (currentSize == array.size() - 1)array.resize(array.size() * 2);
	int hole = ++currentSize;//hole记录的是空穴，要理解代码就要做到心中有图
	array[0] = x;//哨兵，防止直接插入最小值，导致在循环中，空穴直接到了0，当然也可以直接加入if语句判断，不过会增加循环开销
	for (; array[hole / 2] > x;hole/=2) {//三步，第一步，比较父亲与插入节点的大小；第二步，父亲进入空穴；第三步，空穴上移；
		array[hole] = array[hole/2];
	}
	array[hole] = move(array[0]);
}
template<typename T>
void BinaryHeap<T>::deleteMin() {
	if (currentSize == 0) return;
	percolateDown(array[currentSize--]);
}
//两个不对外开放的函数
template<typename T>
void BinaryHeap<T>::buildHeap() {
	for (int i = currentSize / 2; i > 0; --i) {
		percolateDown(i);
	}
}
template<typename T>
void BinaryHeap<T>::percolateDown(int hole) {
	int child = hole;
	T temp = move(array[hole]);
	for (; hole * 2 <= currentSize; hole = child) {
		child = hole * 2;
		//第一步先找到最小的孩子；第二步和hole比较，并且将hole填上最小的孩子
		if (child != currentSize && array[child + 1] < array[child]) {
			++child;
		}
		if (temp > array[child]) {
			array[hole] = array[child];
		}
		else break;
	}
	array[hole] = temp;
}

?对于函数的具体上滤、下滤、建堆的过程与时间消耗，建议直接看书，书上讲的挺好的

3、STL

头文件 #include<queue>

默认是最大堆（大顶堆）

priority_queue<int> maxHeap;

最小堆（小顶堆）

priority_queue<int,vector<int>,greater<int>> minHeap;

核心函数：

push(const Object& x);
Object& top();
void pop();
bool empty();
void clear();

所以还是比较简单的数据结构了。（关于合并操作，不作深入探讨，有兴趣可以看书）