左偏树或左偏堆是使用二叉堆的变体实现的优先队列。每个节点都有一个s值(或等级或距离)到最近的叶子的距离。与二叉堆相反(始终是完整的二叉树), 左偏树可能非常不平衡。
以下是时间复杂度of左偏树/堆.
Function Complexity Comparison
1) Get Min: O(1) [same as both Binary and Binomial]
2) Delete Min: O(Log n) [same as both Binary and Binomial]
3) Insert: O(Log n) [O(Log n) in Binary and O(1) in
Binomial and O(Log n) for worst case]
4) Merge: O(Log n) [O(Log n) in Binomial]
左偏树是具有属性的二叉树:
- 普通最小堆性质:键(i)> =键(父(i))
- 左侧较重:dist(right(i))<= dist(left(i))。在这里, dist(i)是扩展的二叉树表示中从节点i到叶节点的最短路径上的边数(在此表示中, 空子级被视为外部或叶节点)。到达后代外部节点的最短路径是通过正确的子节点。每个子树也是左偏树, dist(i)= 1 + dist(right(i))。
例子:下面的左手树显示了通过上述过程为每个节点计算的距离。最右边的节点的等级为0, 因为此节点的右边子树为null, 并且其父节点的距离为1 x dist(i)= 1 + dist(right(i))。每个节点都遵循相同的规则, 并计算其s值(或等级)。
从以上第二个属性, 我们可以得出两个结论:
- 从根到最右叶的路径是从根到叶的最短路径。
- 如果到最右边的叶子的路径有x个节点, 则左边的堆至少有2个X– 1个节点。这意味着对于具有n个节点的左偏堆, 最右叶的路径长度为O(log n)。
操作方式:
- 主要操作是merge()。
- deleteMin()(或extractMin())可以通过删除根并为左右子树调用merge()来完成。
- 可以通过使用单个键(要插入的键)创建左偏树并为给定树和具有单个节点的树调用merge()来完成insert()。
合并背后的想法:
由于右子树较小, 因此其思想是将一棵树的右子树与其他树合并。以下是抽象步骤。
- 将值较小的根作为新根。
- 将其左子树挂在左侧。
- 递归合并其右子树和另一棵树。
- 从递归返回之前:
–更新合并根目录的dist()。
–如果需要, 在根目录下交换左右子树, 以保持合并的leftist属性
结果
资源 :http://courses.cs.washington.edu/courses/cse326/08sp/lectures/05-leftist-heaps.pdf
合并的详细步骤:
- 比较两个堆的根。
- 将较小的键推入一个空堆栈, 然后移至较小键的右子项。
- 递归比较两个键, 然后继续将较小的键推入堆栈, 然后移至其正确的子级。
- 重复直到达到空节点。
- 以最后处理的节点为准, 使其成为堆栈顶部节点的右子节点, 如果违反了leftist堆的属性, 则将其转换为leftist堆。
- 递归地继续从堆栈中弹出元素, 并使它们成为新堆栈顶部的正确子元素。
例子:
考虑下面给出的两个左偏堆:
将它们合并为一个左偏堆
节点7的子树侵犯了左偏堆的属性, 因此我们将其与左子节点交换并保留了左偏堆的属性。
转换为左偏堆。重复这个过程
该算法在最坏情况下的时间复杂度在最坏情况下为O(log n), 其中n是左偏堆中的节点数。
合并两个左偏堆的另一个示例:
左偏树/左偏堆的实现:
//C++ program for leftist heap / leftist tree
#include <bits/stdc++.h>
using namespace std;
// Node Class Declaration
class LeftistNode
{
public :
int element;
LeftistNode *left;
LeftistNode *right;
int dist;
LeftistNode( int & element, LeftistNode *lt = NULL, LeftistNode *rt = NULL, int np = 0)
{
this ->element = element;
right = rt;
left = lt, dist = np;
}
};
//Class Declaration
class LeftistHeap
{
public :
LeftistHeap();
LeftistHeap(LeftistHeap &rhs);
~LeftistHeap();
bool isEmpty();
bool isFull();
int &findMin();
void Insert( int &x);
void deleteMin();
void deleteMin( int &minItem);
void makeEmpty();
void Merge(LeftistHeap &rhs);
LeftistHeap & operator =(LeftistHeap &rhs);
private :
LeftistNode *root;
LeftistNode *Merge(LeftistNode *h1, LeftistNode *h2);
LeftistNode *Merge1(LeftistNode *h1, LeftistNode *h2);
void swapChildren(LeftistNode * t);
void reclaimMemory(LeftistNode * t);
LeftistNode *clone(LeftistNode *t);
};
// Construct the leftist heap
LeftistHeap::LeftistHeap()
{
root = NULL;
}
// Copy constructor.
LeftistHeap::LeftistHeap(LeftistHeap &rhs)
{
root = NULL;
* this = rhs;
}
// Destruct the leftist heap
LeftistHeap::~LeftistHeap()
{
makeEmpty( );
}
/* Merge rhs into the priority queue.
rhs becomes empty. rhs must be different
from this.*/
void LeftistHeap::Merge(LeftistHeap &rhs)
{
if ( this == &rhs)
return ;
root = Merge(root, rhs.root);
rhs.root = NULL;
}
/* Internal method to merge two roots.
Deals with deviant cases and calls recursive Merge1.*/
LeftistNode *LeftistHeap::Merge(LeftistNode * h1, LeftistNode * h2)
{
if (h1 == NULL)
return h2;
if (h2 == NULL)
return h1;
if (h1->element < h2->element)
return Merge1(h1, h2);
else
return Merge1(h2, h1);
}
/* Internal method to merge two roots.
Assumes trees are not empty, and h1's root contains
smallest item.*/
LeftistNode *LeftistHeap::Merge1(LeftistNode * h1, LeftistNode * h2)
{
if (h1->left == NULL)
h1->left = h2;
else
{
h1->right = Merge(h1->right, h2);
if (h1->left->dist < h1->right->dist)
swapChildren(h1);
h1->dist = h1->right->dist + 1;
}
return h1;
}
// Swaps t's two children.
void LeftistHeap::swapChildren(LeftistNode * t)
{
LeftistNode *tmp = t->left;
t->left = t->right;
t->right = tmp;
}
/* Insert item x into the priority queue, maintaining
heap order.*/
void LeftistHeap::Insert( int &x)
{
root = Merge( new LeftistNode(x), root);
}
/* Find the smallest item in the priority queue.
Return the smallest item, or throw Underflow if empty.*/
int &LeftistHeap::findMin()
{
return root->element;
}
/* Remove the smallest item from the priority queue.
Throws Underflow if empty.*/
void LeftistHeap::deleteMin()
{
LeftistNode *oldRoot = root;
root = Merge(root->left, root->right);
delete oldRoot;
}
/* Remove the smallest item from the priority queue.
Pass back the smallest item, or throw Underflow if empty.*/
void LeftistHeap::deleteMin( int &minItem)
{
if (isEmpty())
{
cout<< "Heap is Empty" <<endl;
return ;
}
minItem = findMin();
deleteMin();
}
/* Test if the priority queue is logically empty.
Returns true if empty, false otherwise*/
bool LeftistHeap::isEmpty()
{
return root == NULL;
}
/* Test if the priority queue is logically full.
Returns false in this implementation.*/
bool LeftistHeap::isFull()
{
return false ;
}
// Make the priority queue logically empty
void LeftistHeap::makeEmpty()
{
reclaimMemory(root);
root = NULL;
}
// Deep copy
LeftistHeap &LeftistHeap::operator =(LeftistHeap & rhs)
{
if ( this != &rhs)
{
makeEmpty();
root = clone(rhs.root);
}
return * this ;
}
// Internal method to make the tree empty.
void LeftistHeap::reclaimMemory(LeftistNode * t)
{
if (t != NULL)
{
reclaimMemory(t->left);
reclaimMemory(t->right);
delete t;
}
}
// Internal method to clone subtree.
LeftistNode *LeftistHeap::clone(LeftistNode * t)
{
if (t == NULL)
return NULL;
else
return new LeftistNode(t->element, clone(t->left), clone(t->right), t->dist);
}
//Driver program
int main()
{
LeftistHeap h;
LeftistHeap h1;
LeftistHeap h2;
int x;
int arr[]= {1, 5, 7, 10, 15};
int arr1[]= {22, 75};
h.Insert(arr[0]);
h.Insert(arr[1]);
h.Insert(arr[2]);
h.Insert(arr[3]);
h.Insert(arr[4]);
h1.Insert(arr1[0]);
h1.Insert(arr1[1]);
h.deleteMin(x);
cout<< x <<endl;
h1.deleteMin(x);
cout<< x <<endl;
h.Merge(h1);
h2 = h;
h2.deleteMin(x);
cout<< x << endl;
return 0;
}
输出如下:
1
22
5
参考文献:
维基百科-左偏树
CSC378:左偏树
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。