数据结构之斜堆的定义与实现

发表于 | 分类于

斜堆基础知识

斜堆又称为自调节堆。其和左式堆最大的区别是不保留零路径长信息以及不做结构限制，可以总结为斜堆是具有堆序的二叉树，但是对结构不做任何限制。其所有操作最坏情况O(n)，每次操作的摊还时间为O(log2n)。和左式堆相似，斜堆的主要操作也是合并，但斜堆除了右路径上最大者不交换左右子节点，其余合并操作必须无条件交换左右子节点。

从斜堆的定义可以知道，所有的左式堆都是斜堆，斜堆一般具有如下性质：

  • 仅有一个节点的树为斜堆
  • 两个斜堆合并的结果仍为斜堆
  • 任意节点关键字值小于等于左右子节点关键字值

斜堆的实现

斜堆相当于一个简化版的左式堆，因此实现起来可以直接在左式堆的代码上进行修改，斜堆主要包含的操作有：

  • 返回最小值：FindMin
  • 合并两个斜堆:Merge
  • 删除最小值（出队）:DeleteMin
  • 插入一个节点：InsertElement

直接套用左式堆的定义有：

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
template <typename DataType>
struct Node
{
	DataType data;
	Node *left;
	Node *right;
	Node(DataType inData):data(inData), left(nullptr), right(nullptr) {} 
};


template <typename DataType>
class SelfAdjustingHeap
{
public:
	SelfAdjustingHeap(): root(nullptr) {}
	~SelfAdjustingHeap();
	DataType FindMin();
	void Merge(Node<DataType> *inTree);
	void DeleteMin();
	void InsertElement(DataType inElement);
	bool IsEmpty();
	void MakeEmpty();
private:
	Node<DataType> *MergeCore(Node<DataType> *inTree1, Node<DataType> *inTree2);
	Node<DataType> *root;
};

如上所示节点数据结构中删除了零路径长的成员，其余和左式堆的定义相同，以下分别实现各函数。

  • 查找最小元素，如果为空则抛出异常
1
2
3
4
5
6
7
8
template <typename DataType>
DataType SelfAdjustingHeap<DataType>::FindMin()
{
	if (root == nullptr) {
		throw "Self adjusting heap is empty!";
	}
	return root->data;
}
  • 合并两棵斜堆核心函数，不再考虑零路径长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename DataType>
Node<DataType> * SelfAdjustingHeap<DataType>::MergeCore(Node<DataType> *inTree1, Node<DataType> *inTree2)
{
	if (inTree1 == nullptr) {
		return inTree2;
	}

	if (inTree2 == nullptr) {
		return inTree1;
	}
	if (inTree1->data > inTree2->data) {
		swap(inTree1, inTree2); //STL库函数
	}
	if (inTree1->left == nullptr) {
		inTree1->left = inTree2;
	}
	else {
		inTree1->right = MergeCore(inTree1->right, inTree2);
		swap(inTree1->left, inTree1->right);
	}
	return inTree1;
}
  • 合并两棵斜堆
1
2
3
4
5
template <typename DataType>
void SelfAdjustingHeap<DataType>::Merge(Node<DataType> *inTree)
{
	root = MergeCore(root, inTree);
}
  • 删除最小元素，拆解为左右两棵子树，然后调用合并函数进行合并
1
2
3
4
5
6
7
template <typename DataType>
void SelfAdjustingHeap<DataType>::DeleteMin()
{
	Node<DataType> *tmp = root;
	root = MergeCore(root->left, root->right);
	delete tmp;
}
  • 插入，转变为单节点斜堆的合并
1
2
3
4
5
6
template <typename DataType>
void SelfAdjustingHeap<DataType>::InsertElement(DataType inElement)
{
	Node<DataType> *newNode = new Node<DataType>(inElement);
	root = MergeCore(root, newNode);
}
  • 判断斜堆是否为空
1
2
3
4
5
template <typename DataType>
bool SelfAdjustingHeap<DataType>::IsEmpty()
{
	return root == nullptr;
}
  • 清空斜堆，采用非递归中序遍历清空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename DataType>
void SelfAdjustingHeap<DataType>::MakeEmpty()
{
	if (root == nullptr) {
		return;
	}
	Node<DataType> *cycleIter = root;
	stack<Node<DataType> *> nodeStack;
	while (cycleIter != nullptr || !nodeStack.empty()) {
		while (cycleIter != nullptr) {
			nodeStack.push(cycleIter);
			cycleIter = cycleIter->left;
		}
		if (!nodeStack.empty()) {
			Node<DataType> *tmp = nodeStack.top();
			cycleIter = tmp->right;
			delete tmp; nodeStack.pop();
		}
	}
	root = nullptr;
}
  • 析构函数，回收内存
1
2
3
4
5
template <typename DataType>
SelfAdjustingHeap<DataType>::~SelfAdjustingHeap()
{
	MakeEmpty();
}