算法导论 第19章 二项堆
发布时间
阅读量：
阅读量
二项堆
二项堆是一种递归定义的数据结构，在计算机科学中常用于高效实现优先队列。它由多棵二项树组成：
基本定义：
- 每一棵二项树满足最小堆性质：根节点的键值不大于所有子节点的键值。
- 根据高度的不同层次有特定的特性：
- 深度为k的树有2ᵏ个节点。
- 第i层恰好有C(k, i)个节点（C为组合数）。
- 根节点的度为k（大于任何其他节点）。
- 子节点从左到右按层次排列成单链表。
性质：- 最大容量为n=2ᵏ⁺¹−1时拥有k+1棵树。
- 通过n的二进制表示判断包含哪些树（每棵树对应一个bit位为1的情况）。
操作：- 合并：将两个符合规定的最小堆合并成一个新的最小堆。
- 插入元素：通过构建新树并将其插入到正确的位置来实现合并操作。
- 查找最小元素：返回最小值所在的根结点。
- 删除最小元素：通过查找前驱结点调整后删除该元素，并重建结构以保持不变性。
算法效率分析：- 插入、删除、查找和合并的时间复杂度主要取决于树的高度和数量级差异。这些操作通常在O(log n)时间内完成。
应用示例：- 使用n次成功插入生成含有n个元素的所有可能大小的最小堆实例来说明如何构建不同规模的小顶堆结构。
通过以上分析可以清晰地理解二项堆在数据结构中的重要性和高效性特点。
二项树
二项树与多数树类型相似，在其构建过程中同样遵循了递归原理。如图所示，在这种结构中，基例B₀仅包含一个单一节点。而对于任意k≥1的情况而言，则可将其视为由两个子结构B_{k-1}通过共享其根节点的左子位实现连接。这种递进方式使得二项树系列能够逐步生成具有不同深度的复杂结构。
二项树的性质
对于二项树Bk，有如下性质：
1、有2^k个节点；
2、树高为k;
3、在深度i处，恰好有
个节点；
4、该结构中核心元素具有最大度值k（即deg(v)=k），并且其所有直接后继（即直接子节点）按顺序排列时每个后继元素对应的子树高度依次减少1直至达到最低层（高度=0）。具体而言，在此结构中第i个直接后继元素对应的子树Bi以其自身作为根节点
二项堆定义
二项堆H又满足下面两个二项堆性质的二项树组成：
所有二项树都符合最小堆的特性，并且每个节点的关键字都不小于其父节点的值；这构成了一个最小二项堆；类似地，我们还可以定义最大二项堆。
2、对于任意非负整数k，在H中至多有一颗度为k的树。
其他性质：
1、对于一个含有n个节点的二项堆，最多含有lgn + 1(向下取整)棵二项树。
2、由n个节点构成的二项堆，在其二进制表示式写作<bk bk-1 ... b₁.b₀>的情况下，在每一层中存在度数为i的情况时，则对应bit位bk-i=1；例如，在一个拥有8个节点（即二进制中的'...'）的情况中（如具体数值），其相应的层次结构可由相应的bit位确定。
二项堆的表示
二项堆节点结构
template < typename K, typename V>
struct binomial_heap_node
{//二项树节点
K key;//键
V value;//值
size_t degree = 0;//度
binomial_heap_node *parent = nullptr;
binomial_heap_node *leftchild = nullptr;
binomial_heap_node *sibling = nullptr;
binomial_heap_node(const K &k, const V &v) :key(k), value(v){}
};二项堆的结构，如下图：
可以观察到，在横向排列上，该树的所有子节点构成一个单链表结构；其中每个子节点的头指针均指向整个层级的顶层链表。
二项堆的操作
1、make-heap:创建一个空二项堆；
2、insert:向堆中插入一个元素；
3、minimum:返回最小堆的极小值；
4、extract-min:返回堆极小值，并删掉它；
5、union：合并两个堆；
6、decrease:减少某个元素的键，并调整堆；
7、erase:删除某一元素。
算法就不讨论了，算法导论上讲得很明白，直接给出代码，注释标明一切
#include<iostream>
#include<utility>
#define EXTREMUM 0x7fffffff //极值，取极大值则最小堆，取极小值则最大堆
using namespace std;
template < typename K, typename V>
struct binomial_heap_node
{//二项树节点
K key;//键
V value;//值
size_t degree = 0;//度
binomial_heap_node *parent = nullptr;
binomial_heap_node *leftchild = nullptr;
binomial_heap_node *sibling = nullptr;
binomial_heap_node(const K &k, const V &v) :key(k), value(v){}
};
template <typename K, typename V, typename Compare = less<K> >
class binomial_heap
{//二项堆，左孩子右兄弟方式存储
public:
typedef binomial_heap_node<K, V> node;
typedef binomial_heap Bheap;
private:
node *head;
Compare compare;//键比较器，默认小于，为最小堆
void heapLink(node *lhs, node *rhs)
{//两棵二项树的链接
lhs->parent = rhs;
lhs->sibling = rhs->leftchild;
rhs->leftchild = lhs;
++rhs->degree;
}
void linkAtTail(node *&tail,node *curr)
{//尾插法链二项树
if (head == nullptr)
{
head = curr;
tail = curr;
}
else
{
tail->sibling = curr;
tail = tail->sibling;
}
}<pre class="cpp" name="code"> node* findPre(node *curr)const
{//查找curr的前驱
node *pre = nullptr;
if (curr->parent == nullptr) pre = head;
else if (curr->parent->leftchild == curr) return pre;
else pre = curr->parent->leftchild;
while (pre->sibling != curr)
pre = pre->sibling;
return pre;
}
void heapMerge(binomial_heap&);
void postTraversal(node *)const;
void destroy(node*);
void reverse();
public:
binomial_heap(node *h, Compare c = Compare()) :head(h), compare(c){}
binomial_heap(Compare c = Compare()) :head(nullptr), compare(c){}
void insert(const K&, const V&);
node* minimum()const;
pair<K, V> extractMin();
void BheapUnion(binomial_heap&);
void decreaseKey(node*, const K&);
void erase(node*);
bool empty()const { return head == nullptr; }
void print()const { postTraversal(head); }
~binomial_heap(){ destroy(head); }
};
template <typename K,typename V,typename Compare>
void binomial_heap<K, V, Compare>::insert(const K &k, const V &v)
{//插入元素
node *curr = new node(k, v);
if (head == nullptr) head = curr;//若为第一个节点
else
{//否则
binomial_heap heap(curr,compare);
BheapUnion(heap);
}
}
template <typename K,typename V,typename Compare>
binomial_heap_node<K, V>* binomial_heap<K, V, Compare>::minimum()const
{//寻找最小/大元素，返回指针
node *p_min = nullptr, *curr = head;
K min = EXTREMUM;
while (curr != nullptr)
{
if (compare(curr->key,min))
{
min = curr->key;
p_min = curr;
}
curr = curr->sibling;
}
return p_min;
}
template <typename K,typename V,typename Compare>
pair<K, V> binomial_heap<K, V, Compare>::extractMin()
{//获得最小/大值，返回pair<K,V>，即键值对
node *p_min = nullptr, *pre = nullptr, *curr = head;
K min = head->key;//初始时head即为最值
while (curr->sibling != nullptr)
{//迭代，寻得最值，及其前驱
if (compare(curr->sibling->key,min))
{
min = curr->sibling->key;
pre = curr;
}
curr = curr->sibling;
}
if (pre == nullptr)
{//若只有一个元素或者第一个元素即为所求
p_min = head;
head = p_min->sibling;
}
else
{//否则
p_min = pre->sibling;
pre->sibling = p_min->sibling;
}
binomial_heap heap(p_min->leftchild,compare);//创建临时二项堆
heap.reverse();//先逆置
BheapUnion(heap);//再和原来的堆合并
pair<K, V> return_value = pair<K, V>(p_min->key, p_min->value);//构造返回值
delete p_min;//释放节点内存
return return_value;
}
template <typename K,typename V,typename Compare>
void binomial_heap<K, V, Compare>::BheapUnion(binomial_heap &rhs)
{//二项堆的合并
heapMerge(rhs);//先将两条链合并，按度的非递减顺序
if (head == nullptr) return;
node *prev = nullptr, *curr = head, *next = head->sibling;
while (next != nullptr)
{//遍历每一个二项树的根
if ((curr->degree != next->degree) || (next->sibling != nullptr && next->sibling->degree
== curr->degree))
{//若当前树和下一棵树度不等，或者有三颗二项树的根的度相等
prev = curr;
curr = next;
}//否则当前仅有两棵树度相等
else if (compare(curr->key,next->key))
{//若当前树的根的key较小
curr->sibling = next->sibling;
heapLink(next, curr);//则将下一棵二项树链为其左孩子
}
else
{//否则，相反
if (prev == nullptr) head = next;//若当前二项堆最前面两棵树的度相等，则修改head
else prev->sibling = curr->sibling;
heapLink(curr, next);
curr = next;
}
next = curr->sibling;
}
}
template <typename K,typename V,typename Compare>
void binomial_heap<K, V, Compare>::decreaseKey(node *p, const K &k)
{//减小某一节点的key，并调整堆，则该函数其实就是increaseKey
if (!compare(k,p->key))
{//若新值较大
cout << "Error : greater key" << endl;
return;
}
p->key = k;
node *par = p->parent,*p_sib = p->sibling;
while (par != nullptr && compare(p->key,par->key))
{//自底向上调整
//修改p和par的后继，即右兄弟
p->sibling = par->sibling;
par->sibling = p_sib;
//如果p和par存在前驱，则修改它们前驱的右兄弟
node *p_pre, *par_pre;
if ((p_pre = findPre(p)) != nullptr)
p_pre->sibling = par;
if ((par_pre = findPre(par)) != nullptr)
par_pre->sibling = p;
if (par->parent != nullptr && par->parent->leftchild == par)
par->parent->leftchild = p;
node *p_child = p->leftchild;
//设置p的孩子
if (p->parent->leftchild == p)//如果p是其父亲par的左孩子，p的祖先其实就是par
p->leftchild = par;
else
{//否则
p->leftchild = par->leftchild;
par->leftchild->parent = p;
}
p->parent = par->parent;//设置p的祖先
par->parent = p;//设置par的祖先
//设置par的孩子
par->leftchild = p_child;
if (p_child != nullptr)
p_child->parent = par;
std::swap(p->degree, par->degree);//交换度
par = p->parent;
}
}
template <typename K,typename V,typename Compare>
void binomial_heap<K,V,Compare>::erase(node *p)
{//删除指定节点
node *p_min = minimum();
decreaseKey(p, p_min->key - 1);
extractMin();
}
template <typename K,typename V,typename Compare>
void binomial_heap<K, V, Compare>::heapMerge(binomial_heap &rhs)
{//按度非递减顺序合并两个堆
if (rhs.empty()) return;//若至少有一堆空
if (empty())
{
head = rhs.head;
rhs.head = nullptr;
return;
}
node *curr1 = head, *curr2 = rhs.head,*tail = nullptr;
head = nullptr, rhs.head = nullptr;
while (curr1 != nullptr && curr2 != nullptr)
{//不断链接，直到有一堆为空
if (curr1->degree <= curr2->degree)
{
linkAtTail(tail,curr1);//尾端链入
curr1 = curr1->sibling;
}
else
{
linkAtTail(tail,curr2);
curr2 = curr2->sibling;
}
}
if (curr1 != nullptr) tail->sibling = curr1;//若本堆还有剩下
else if (curr2 != nullptr) tail->sibling = curr2;//若另一堆还有剩下
else tail->sibling = nullptr;//若均没有剩下
}
template <typename K,typename V,typename Compare>
void binomial_heap<K, V, Compare>::destroy(node *H)
{//销毁堆
node *curr = H;
while (curr != nullptr)
{//销毁每一棵二项树
destroy(curr->leftchild);//递归销毁每一个子堆
node *p = curr;
curr = curr->sibling;
delete p;//释放该树根
}
}
template <typename K,typename V,typename Compare>
void binomial_heap<K, V, Compare>::reverse()
{//逆置
node *curr = head,*r;
head = nullptr;
while (curr != nullptr)
{
curr->parent = nullptr; r = curr;
curr = curr->sibling;
if (head == nullptr)
{
head = r;
r->sibling = nullptr;
}
else
{
r->sibling = head;
head = r;
}
}
}
template <typename K,typename V,typename Compare>
void binomial_heap<K, V, Compare>::postTraversal(node *H)const
{//后序遍历二项堆
node *curr = H;
while (curr != nullptr)
{
postTraversal(curr->leftchild);//递归
printf("key: %-6d value: %-6d degree: %-6d\n", curr->key, curr->value,curr->degree);
curr = curr->sibling;
}
}
int main()
{ <pre class="cpp" name="code"> binomial_heap<int, int> bh;
vector<binomial_heap_node<int, int>*> ptr(10);
for (int i = 0; i != 10; i++)
ptr[i] = bh.insert(i, 2 * i);
for (size_t i = 0; i != ptr.size(); ++i)
cout << ptr[i]->key << ' ';
cout << endl;
//binomial_heap_node<int, int> *p = bh.minimum();
for (size_t i = 0; i != ptr.size(); i += 2)
bh.decreaseKey(ptr[i], ptr[i]->key - 2);
for (size_t i = 0; i != ptr.size(); ++i)
cout << ptr[i]->key << ' ';
cout << endl;
bh.print();
cout << endl;
while (!bh.empty())
{
cout << bh.minimum()->key << endl;
bh.extractMin();
}
getchar();
return 0;
}习题 19.2-1 见程序代码
习题 19.2-5
在堆的数据结构中,如果某个节点的关键字值为无穷大,则会导致无法找到该节点,从而返回地址为空.建议将条件语句中的'<'符号替换为'≤',以便更好地满足算法需求.
习题 19.2-6
BINOMIAL-HEAP-DELETE(H,x)
{
y <- BINOMIAL-HEAP-MINIMUM();
BINOMIAL-HEAP-DECREASE-KEY(H,x,key[y] - 1);
BINOMIAL-HEAP-EXTRACT-MIN()
}习题 19.2-7
对于二项堆H，若存在度为k的二项树，则二进制数（设为x）的第k+1位为1.
1、插入一个节点，对应到x上就是，x = x + 1；
2、合并两个堆（设另一个堆对应地二进制数为y），就是，x = x + y。
当发生进位时, 表明有相同次数的二项式树存在, 并且这些树将进行合并, 形成次数加1的新二项式树.
习题 19.2-8
参考19.2-7所述内容，在算法实现中设变量x等于序列<bk.bk-1...b1.b0>（其中bk表示最高位）。每次插入一个节点相当于x递增1的操作，在此过程中需要考虑是否存在进位操作：若无进位，则操作完成；若有进位，则需持续进行直到找到第一个未被置为1的位置。对于具体的二项堆结构而言，在构建时需要遵循从左到右合并的方式进行处理：当初始状态不存在度为0的二项树（即只有一个根节点的零次方树）时，则合并过程停止；否则需要执行合并操作以生成度数加一的新二项树，并在此基础上继续操作直至满足合并条件。
习题19.2-9
相当于对顶层链表进行反转，并同时完成各项操作。其反转所需的时间为O(lgn)，这表明整个操作的时间复杂度仍保持不变。
思考题19-2
基于二项堆构建的最小生成树算法
全部评论 (0)
还没有任何评论哟~