提醒

注意vector元素之间赋值要调用move函数

二叉堆结构性质

类的声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#pragma one
#include<vector>
#include<iostream>
using namespace std;

template<typename Comparable>
class BinaryHeap
{
public:
	 explicit BinaryHeap(vector<Comparable>& items)
		:this->array(items.size()+10),this->currentSize(items.size())
	{
		for (int i = 0; i < items.size(); i++)
		{
			this->array[i + 1] = items[i];
		}
		this->buildHeap();
	}

	bool isEmpty();
	const Comparable& findMin();

	void insert(Comparable& x);
	void deleteMin();
	void deleteMin(Comparable& minItem);//把最小值赋值给minItem并删除
	void makeEmpty();
private:
	int currentSize;//堆中元素个数
	vector<Comparable> array;//存储堆中元素的数组
	void buildHeap();
	void percolateDown(int hole);
	void percolateUp(int hole);
};

类成员函数定义（部分重点函数）

percolateDown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename Comparable>
inline void BinaryHeap<Comparable>::percolateDown(int hole)//下滤
{
	int child;
	Comparable temp = move(this->array[hole]);
	for (; hole * 2 <= currentSize; hole =child)
	{
		child = hole * 2;
		if (child != currentSize && this->array[child + 1] < this->array[child])
			child++;//若存在两个子节点则child为两个子节点中较大的节点
		if (this->array[child] < temp)
			this->array[hole] = move(this->array[child]);
		else
			break;
	}
	this->array[hole] = move(temp);
}

percolateUp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename Comparable>
inline void BinaryHeap<Comparable>::percolateUp(int hole)//上滤
{
	int father;
	Comparable temp = move(this->array[hole]);
	for (; hole / 2 > 0; hole = father)
	{
		father = hole / 2;
		if (temp < this->array[father])
		{
			this->array[hole] = move(this->array[father]);
		}
		else break;
	}
	this->array[hole] = temp;
}

buildHeap

1
2
3
4
5
6
template<typename Comparable>
inline void BinaryHeap<Comparable>::buildHeap()
{
	for (int i = currentSize / 2; i > 0; i--)
		percolateDown(i);
}

insert

1
2
3
4
5
6
template<typename Comparable>
void BinaryHeap<Comparable>::insert(Comparable& x)
{
	array[++currentSize] = x;
	percolateUp(currentSize);
}

deleteMin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename Comparable>
void BinaryHeap<Comparable>::deleteMin()//删除最小值
{
	if (isEmpty())
		throw UnderflowException();
	array[1] = move(array[currentSize--]);
	percolateDown(1);
}
//------------------------------------------------------
template<typename Comparable>
void BinaryHeap<Comparable>::deleteMin(Comparable& minItem)//删除并把最小值赋值给minItem
{
	if (isEmpty())
		throw UnderflowException();
	minItem = move(array[1]);
	array[1] = move(array[currentSize--]);
	percolateDown(1);
}