结构之美——优先队列基本结构(四)——二叉堆、d堆、左式堆、斜堆

实现优先队列结构主要是通过堆完成,主要有:二叉堆、d堆、左式堆、斜堆、二项堆斐波那契堆pairing 堆等。

 

1. 二叉堆 

1.1. 定义

完全二叉树,根最小。

存储时使用层序。

 

1.2. 操作

(1). insert(上滤)

插入末尾 26,不断向上比较,大于26则交换位置,小于则停止。

 

(2). deleteMin(下滤)

提取末尾元素,放在堆顶,不断下滤:

 

(3). 其他操作:

都是基于insert(上滤)与deleteMin(下滤)的操作。

减小元素:减小节点的值,上滤调整堆。

增大元素:增加节点的值,下滤调整堆。

删除非顶点节点:直接删除会出问题。方法:减小元素的值到无穷小,上滤后删除。

Merge:insert one by one

 

2. d叉堆

2.1. 定义

完全d叉树,根最小。

存储时使用层序。

 

2.2. 操作:

操作跟二叉堆基本一致:insert,deleteMin,增大元素,减小元素,删除非顶元素,merge。

 

2.3 二叉堆与d叉堆的对比:

 

3. 左式堆

3.1. 定义

零路径长度:到没有两个儿子的节点最短距离

左式堆:

1.一棵二叉树

2.零路径长:左儿子≧右儿子,父节点= min{儿子} +1(这条性质导致了左式堆的严重左偏)

 

零路径长度:

 

 

 

3.2. 操作:

(1) merge :

原则:根值大的堆与根值小的堆的右子堆合并(根值:根位置的元素值,并非零路径长度)

 

 

具体分三种情况(设堆H1的根值小于H2)

H1只有一个节点

H1根无右孩子

H1根有右孩子

 

(1.1).H1只有一个节点,若出现不满足:零路径长:左儿子≧右儿子,交换左右孩子。

 

(1.2).H1根无右孩子,若出现不满足:零路径长:左儿子≧右儿子,交换左右孩子。

 

 

(1.3).H1根有右孩子

1.初始状态,H1的根6,H2的根为8,将H2合并到H1。

2.将H1构造成根无右孩子的形式:

3.将元素10, merge到H2,要首先将H2构造成根无右孩子的形式,递归,merge,若出现不满足:零路径长:左儿子≧右儿子,交换左右孩子……

——》——》——》

4.

5.

3.3. 性质分析:

insert:merge

deleteMin:delete root,merge

时间复杂度:merge与右路径长度之和成正比;最坏O(logN)

缺点:交换需判断;维护零路径长

 

4. 斜堆

 

4.1. 定义

二叉树,根最小。由此可见:

 

 

 

特点:merge无条件交换。

 

时间复杂度:最坏O(N);最好Ω(1);平均O(logN)

 

4.2性能比较:

定義

  • 僅有一個節點的樹為斜堆;
  • 兩個斜堆合併的結果仍為斜堆。

合併操作

斜堆合併操作的遞歸合併過程和左偏樹完全一樣。假設我們要合併 A 和 B兩個斜堆,且 A 的根節點比 B 的根節點小,我們只需要把 A 的根節點作為合併後新斜堆的根節點,並將 A 的右子樹與 B 合併。由於合併都是沿著最右路徑進行的,經過合併之後,新斜堆的最右路徑長度必然增加,這會影響下一次合併的效率。所以合併後,通過交換左右子樹,使整棵樹的最右路徑長度非常小(這是啟發規則)。然而斜堆不記錄節點的距離,在操作時,從下往上,沿著合併的路徑,在每個節點處都交換左右子樹。通過不斷交換左右子樹,斜堆把最右路徑甩向左邊了。

遞歸實現合併

  • 比較兩個堆; 設p是具有更小的root的鍵值的堆,q是另一個堆,r是合併後的結果堆。
  • 令r的root是p(具有最小root鍵值),r的右子樹為p的左子樹。
  • 令r的左子樹為p的右子樹與q合併的結果。

舉例。合併前: 

合併後 

非遞歸合併實現

  • 把每個堆的每棵(遞歸意義下)最右子樹切下來。這使得得到的每棵樹的右子樹均為空。
  • 按root的鍵值的升序排列這些樹。
  • 迭代合併具有最大root鍵值的兩棵樹:
    • 具有次大root鍵值的樹的右子樹必定為空。把其左子樹與右子樹交換。現在該樹的左子樹為空。
    • 具有最大root鍵值的樹作為具有次大root鍵值樹的左子樹。

舉例: 

5. 总结

 

如果是不支持所谓的合并操作union的话,普通的堆数据结构就是一种很理想的数据结构(堆排序)。 但是如果想要支持集合上的合并操作的话,最好是使用二项堆或者是斐波那契堆,普通的堆在union操作上最差的情况是O(n),但是二项堆和斐波那契堆是O(lgn)。

时间: 2024-10-29 00:02:41

结构之美——优先队列基本结构(四)——二叉堆、d堆、左式堆、斜堆的相关文章

大话数据结构十三:二叉树的链式存储结构(二叉链表)

1. 关于树 ① 树的度 - 也即是宽度,简单地说,就是结点的分支数. ② 树的深度 - 组成该树各结点的最大层次. ③ 森林 - 指若干棵互不相交的树的集合. ④ 有序树 - 指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样的树称为有序树,否则称为无序树. 2. 二叉树的特点 i.每个结点最多有两颗子树 ii.左子树和右子树是有顺序的,次序不能任意颠倒 iii.即使树中某结点只有一颗子树,也要区分它是左子树还是右子树 3. 二叉树五种形态 ① 空二叉树 ② 只有一个根结点 ③ 根

c++-怎么在一个结构体里调用本身结构体数组

问题描述 怎么在一个结构体里调用本身结构体数组 typedef struct XML_DATA{ struct XML_DATA DATA[10]; char MENU[10][256]; ezxml_t xml; char *txt; char *strAttr; char *file; };XML_DATA m_data[10]; 这样使用为什么会报错,应该怎么修改?谢谢大家帮忙看看咯. 解决方案 定义变量要使用:struct XML_DATA m_data[10];要不就要改结构体的定义,

优先队列之二叉堆与d-堆

二叉堆简介   平时所说的堆,若没加任何修饰,一般就是指二叉堆.同二叉树一样,堆也有两个性质,即结构性和堆序性.正如AVL树一样,对堆的以此操作可能破坏者两个性质中的一个,因此,堆的操作必须要到堆的所有性质都被满足时才能终止. 结构性质   堆是一棵完全填满的二叉树,因为完全二叉树很有规律,所以它可以用一个数组表示而不需要指针.如下图所示,图2中的数组对应图1中的堆.                              图1:二叉堆                             

c语言-结构体指针数组指向结构体类型数组的问题

问题描述 结构体指针数组指向结构体类型数组的问题 #include<stdio.h> #include<stdlib.h> struct student { char num; char name[10]; int grade; }; void swap(struct student *p[],int n) { int k,m,i,j; struct student *d; k=0;m=n-1; while(k<m) { j=m-1;m=0; for(i=k;i<=j;

结构体的函数指针-结构体的函数的指针问题

问题描述 结构体的函数的指针问题 我在a.h中定义了结构体 typedef struct link_t{ int data; struct link_t* prior; struct link_t* next; }Node_t,Link_t; typedef struct{ void (*destory_link)(Link_t head); link_t (*creat_link)(int length); Node_t* (*delete_node)(Node_t node); Node_t

shared pool系列三:library cache结构/library cache object的结构

library cache结构/library cache object的结构-dump LibraryHandle Library cache结构 Library cache最主要的功能就是存放用户提交的SQL语句,SQL语句相关的解析树(解析树也就是对SQL语句中所涉及到的所有对象的展现)--->共享SQL区(shared SQL areas),私有SQL区(private SQLareas,如果配置了共享服务器),执行计划,用户提交的PL/SQL程序块(包括匿名程序块,存储过程,包,函数等

一起学Windows Phone7开发(十四.二 Email Task)

一.Email Task:可以调用系统邮件程序发送邮件. 在发送之前,需要设置一个邮箱帐户,才可以发送,但是完整版的也没有设置 项,看来模拟器上是无法发邮件的,所以连设置项都省了.那只有在真机上才可 以用这个Task了. EmailComposeTask email = new EmailComposeTask(); email.Body = "test my email by wp7 emulator"; email.Subject = "test"; email

结构化数据和非结构化数据是什么意思?

文章中提到的结构化数据.非结构化数据以及半结构化数据是对存储形式的一种数据类型分析,有助于企业细分行业案例,帮助存储合作伙伴更好地解决应用实施方案. 结构化数据,简单来说就是数据库.结合到典型场景中更容易理解,比如企业ERP.财务系统;医疗HIS数据库;教育一卡通;政府行政审批;其他核心数据库等.这些应用需要哪些存储方案呢?基本包括高速存储应用需求.数据备份需求.数据共享需求以及数据容灾需求. 非结构化数据,包括视频.音频.图片.图像.文档.文本等形式.具体到典型案例中,像是医疗影像系统.教育视

什么是结构化数据、非结构化数据?

  文章中提到的结构化数据.非结构化数据以及半结构化数据是对存储形式的一种数据类型分析,有助于企业细分行业案例,帮助存储合作伙伴更好地解决应用实施方案. 结构化数据,简单来说就是数据库.结合到典型场景中更容易理解,比如企业ERP.财务系统;医疗HIS数据库;教育一卡通;政府行政审批;其他核心数据库等.这些应用需要哪些存储方案呢?基本包括高速存储应用需求.数据备份需求.数据共享需求以及数据容灾需求. 非结构化数据,包括视频.音频.图片.图像.文档.文本等形式.具体到典型案例中,像是医疗影像系统.教