您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

二叉堆、斐波那契堆、二项堆是什么?关于数据结构,了解一下

时间:2022-09-29 10:21:39  来源:  作者:51Testing软件测试网

实现优先级队列最常用的数据结构是堆,堆的常见实现有二叉堆、斐波那契堆、二项堆等。

二叉堆

堆是一种完全二叉树,我们以小根堆为例,小根堆的性质就是,每个节点都小于其左孩子和右孩子,不难发现,这种二叉树,根的值是最小的。

堆有以下几种操作:堆的初始化、修改某个值(规定修改之后的值小于等于原来的值)、插入某个值、取出根节点(即取出该优先队列中的优先级最高的值)。

在进行这几种操作的时候,要维护堆的性质。

堆的存储

我们不难发现以下结论:在一棵完全二叉树中,假设节点下标从0开始,那么点i的左孩子的下标为 (i<<1)+1,右孩子的下标为(i<<1)+2 ,父节点的下标为(i-1)>>1,我么可以使用数组来存储这棵完全二叉树。

向下调整

向下调整即调整某个子树成为小根堆,由于小根堆的任意一个子树必定也是小根堆,当我们修改了位于i节点的某个值的时候,假设修改的值不小于原来的值,或者说修改的是根节点,那么如果要保持小根堆的性质,那么必定要判断这个节点是否需要移动,如果需要移动,那么必定是会移动到其子树中,不会向上移动。

所以这时候就要将这个节点和它的两个孩子中的值较小的进行交换,由于完全二叉树的性质,右子树的深度总是小于等于左子树,所以为了这一小点优势,我们通常在两个孩子值相同时,和右孩子交换,然后这时候和他交换的这个孩子又需要调整了,显然也需要向下调整,因此我们递归调用向下调整,直到没有交换,或者到了叶子节点。这个操作的时间复杂度为O (lgn) 。

向上调整

向上调整和向下调整一样,适合将某个节点的值改为比以前更小或者相等的值,或者修改了叶子节点的情况。

在这两种情况下,该节点需要向上移动,就是直接和这个节点的父节点比较,如果比父节点还小,那么就和他的父节点交换,然后递归向上调整它的父节点,直到到达根节点,或者某次没有交换。这个操作的复杂度也是O(logn)。

初始化

完全二叉树的一个显而易见的性质,假设其标号从0开始,到n-1结束,那么从n/2到n-1的点全是叶子节点,叶子节点可以看成是节点数为1的堆,所以说我们如果要构建一个堆,就从(n/2)-1到0点进行向下调整即可。

初始化的时间复杂度乍一看是O(nlogn) ,调整n/2次,每次复杂度是O (logn),这不是O (nlogn) 吗?其实不然,调整n/2次不假,但是并不是每次调整都是O (logn) ,因为每次调整的复杂度取决于调整的子树的高度。

因此,其复杂度小于O (nlogn) ,实际上初始化堆的时间复杂度为O (n) 。

修改某值

假设把下标为i的节点的值改为了key(修改之后的值比之前的小,也就是优先级更高),那么如果要维护堆的性质,就要在该节点处向上调整。该操作的时间复杂度为O (logn)。

插入某值

将新节点插入到末尾,这个新节点必定是叶子节点,那么直接在这个节点上向上调整即可。该操作的时间复杂度为O (logn) 。

获取优先级最高的值并删除

由于二叉堆的性质,根节点的优先级必定是最高的(即节点的值最小)所以获取优先级最高的值只需要将根节点返回即可,如果要删除掉该节点,那么就将最后一个节点放到根节点的位置,然后从根节点处向下调整即可。该操作的时间复杂度为O(logn) 。

二叉堆实现代码

import JAVA.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Heap> {

//堆的规模

private int n;

//具体的堆

private List a;

public Heap(T[] a) {

this.a = new ArrayList<>();

this.a.addAll(Arrays.asList(a));

this.n = this.a.size();

build();

* 初始化堆

public void build() {

for (int i = (n >> 1) - 1; i >= 0; i--) {

down(i);

* 获取父节点的下标

* @param i

* @return

private int parent(int i) {

return (i-1)>>1;

* 获取左孩子的下标

* @param i

* @return

public int left(int i) {

return (i << 1) + 1;

* 获取右孩子的下标

* @param i

* @return

public int right(int i) {

return (i << 1) + 2;

* 向下调整,以满足小根堆的性质

* @param i

public void down(int i) {

int left = left(i);

int right = right(i);

int small = i;

if (left < n && a.get(left).compareTo(a.get(i)) < 0) {

small = left;

if (right < n && a.get(right).compareTo(a.get(small)) < 0) {

small = right;

if (small != i) {

T temp = a.get(i);

a.set(i, a.get(small));

a.set(small, temp);

down(small);

* 向上调整

* @param i

public void up(int i) {

int parent = parent(i);

if (parent >= 0 && a.get(parent).compareTo(a.get(i)) > 0) {

T temp = a.get(i);

a.set(i, a.get(parent));

a.set(parent, temp);

up(parent);

* 将下标为i处的节点值更新为key(变小)

* @param i

* @param key

public void update(int i, T key) {

a.set(i, key);

up(i);

* 插入新的节点key

* @param key

public void insert(T key) {

a.add(key);

n++;

up(n - 1);

* 获取并移除根节点

* @return

public T getTop() {

T result = a.get(0);

a.set(0, a.get(--n));

down(0);

return result;

@Override

public String toString() {

return a.toString();

public static void main(String[] args) {

Integer[] a = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};

Heap heap = new Heap<>(a);

System.out.println(heap);

heap.insert(13);

System.out.println(heap);

heap.update(3, 1);

System.out.println(heap);

斐波那契堆

斐波那契堆(Fibonacci heap)是堆中一种,它和二项堆一样,也是一种可合并堆,可用于实现合并优先队列。斐波那契堆比二项堆具有更好的平摊分析性能,它的合并操作的时间复杂度是O (1) 。

与二项堆一样,它也是由一组堆最小有序树组成,并且是一种可合并堆。与二项堆不同的是,斐波那契堆中的树不一定是二项树,而且二项堆中的树是有序排列的,但是斐波那契堆中的树都是有根而无序的。

基本定义

typedef int Type;

typedef struct _FibonacciNode

Type key; // 关键字(键值)

int degree; // 度数

struct _FibonacciNode *left; // 左兄弟

struct _FibonacciNode *right; // 右兄弟

struct _FibonacciNode *child; // 第一个孩子节点

struct _FibonacciNode *parent; // 父节点

int marked; //是否被删除第1个孩子(1表示删除,0表示未删除)

}FibonacciNode, FibNode;

FibNode是斐波那契堆的节点类,它包含的信息较多。key是用于比较节点大小的,degree是记录节点的度,left和right分别是指向节点的左右兄弟,child是节点的第一个孩子,parent是节点的父节点,marked是记录该节点是否被删除第1个孩子(marked在删除节点时有用)。

typedef struct _FibonacciHeap{

int keyNum; // 堆中节点的总数

int maxDegree; // 最大度

struct _FibonacciNode *min; // 最小节点(某个最小堆的根节点)

struct _FibonacciNode **cons; // 最大度的内存区域

}FibonacciHeap, FibHeap;

FibHeap是斐波那契堆对应的类。min是保存当前堆的最小节点,keyNum用于记录堆中节点的总数,maxDegree用于记录堆中最大度,而cons在删除节点时来暂时保存堆数据的临时空间。

从图中可以看出,斐波那契堆是由一组小根堆组成,这些小根堆的根节点组成了双向链表(根链表),斐波那契堆中的最小节点就是"根链表中的最小节点"!

基本操作

插入操作

插入操作非常简单:插入一个节点到堆中,直接将该节点插入到"根链表的min节点"之前即可;若被插入节点比"min节点"小,则更新"min节点"为被插入节点。

斐波那契堆的根链表是"双向链表",这里将min节点看作双向联表的表头。在插入节点时,每次都是"将节点插入到min节点之前(即插入到双链表末尾)"。

此外,对于根链表中小根堆都只有一个节点的情况,插入操作就很演化成双向链表的插入操作。

* 将"单个节点node"加入"链表root"之前

* a …… root

* a …… node …… root

* 注意: 此处node是单个节点,而root是双向链表

static void fib_node_add(FibNode *node, FibNode *root)

node->left = root->left;

root->left->right = node;

node->right = root;

root->left = node;

* 将节点node插入到斐波那契堆heap中

static void fib_heap_insert_node(FibHeap *heap, FibNode *node)

if (heap->keyNum == 0)

heap->min = node;

else

fib_node_add(node, heap->min);

if (node->key < heap->min->key)

heap->min = node;

heap->keyNum++;

本文作者:中国农业银行研发中心西安研发部 陈登帅



Tags:数据结构   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  Tags: 数据结构  点击:(1)  评论:(0)  加入收藏
实现优先级队列最常用的数据结构是堆,堆的常见实现有二叉堆、斐波那契堆、二项堆等。二叉堆堆是一种完全二叉树,我们以小根堆为例,小根堆的性质就是,每个节点都小于其左孩子和右...【详细内容】
2022-09-29  Tags: 数据结构  点击:(0)  评论:(0)  加入收藏
0. 学习目标在顺序存储方式中,根据数据元素的序号就可随机存取表中任何一个元素,但同时在插入和删除运算需要移动大量的元素,造成算法效率较低。解决此缺陷的一个办法是:对线性...【详细内容】
2022-07-29  Tags: 数据结构  点击:(62)  评论:(0)  加入收藏
和AVL树一样,红黑树也是自平衡二叉搜索树。红黑树同样解决了在特定情况下二叉搜索树会退化成链表的问题。但是红黑树又不像AVL树那样高度平衡,这就让红黑树在插入删除频繁的场...【详细内容】
2022-06-16  Tags: 数据结构  点击:(58)  评论:(0)  加入收藏
概览Redis 本质是 K-V 键值对数据库,底层通过字典 dict 存储键值映射关系,除此之外,dict 还作为 Redis hash 结构底层的实现之一。讨论 Redis 的数据结构,可以从两个层面出发。...【详细内容】
2022-04-18  Tags: 数据结构  点击:(100)  评论:(0)  加入收藏
AVL(Adelson-Velsky and Landis Tree) 树是一种自平衡二叉树, 也是最早发明的一种自动平衡二叉树。原因是由于BST(二叉搜索树)在用有序列表不断插入时会退化成链表而大大影...【详细内容】
2022-03-15  Tags: 数据结构  点击:(118)  评论:(0)  加入收藏
要想知道什么是数据结构?首先得知道数据是什么?数据是对客观事务的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。那为何加上XX“结构”XX两...【详细内容】
2022-02-14  Tags: 数据结构  点击:(0)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: 数据结构  点击:(137)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: 数据结构  点击:(137)  评论:(0)  加入收藏
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Tags: 数据结构  点击:(161)  评论:(0)  加入收藏
▌简易百科推荐
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  掂掂三生有幸  今日头条  Tags:数据结构   点击:(1)  评论:(0)  加入收藏
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  legendarykk  CSDN  Tags:链表   点击:(4)  评论:(0)  加入收藏
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  掂掂三生有幸    Tags:递归算法   点击:(5)  评论:(0)  加入收藏
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  掂掂三生有幸  今日头条  Tags:链表   点击:(2)  评论:(0)  加入收藏
最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类: O(n^2)&mdash;&mdash...【详细内容】
2022-10-01  掂掂三生有幸  今日头条  Tags:排序算法   点击:(1)  评论:(0)  加入收藏
实现优先级队列最常用的数据结构是堆,堆的常见实现有二叉堆、斐波那契堆、二项堆等。二叉堆堆是一种完全二叉树,我们以小根堆为例,小根堆的性质就是,每个节点都小于其左孩子和右...【详细内容】
2022-09-29  51Testing软件测试网     Tags:数据结构   点击:(0)  评论:(0)  加入收藏
简介布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快。但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回tru...【详细内容】
2022-09-13  java保佑我发大财  今日头条  Tags:布隆过滤器   点击:(35)  评论:(0)  加入收藏
1、A GPU accelerated Genetic Algorithm for the Construction of Hadamard Matrices Andras Balogh, Raven Ruiz这篇论文使用遗传算法来构建Hadamard矩阵。 生成随机矩...【详细内容】
2022-09-06  deephub  今日头条  Tags:遗传算法   点击:(51)  评论:(0)  加入收藏
导读:ClickHouse已经成为行业主流且热门的开源引擎。随着业务数据量扩大,场景覆盖变广泛,在复杂query场景下,ClickHouse容易存在查询异常问题,影响业务正常推进。本次主要分享字...【详细内容】
2022-09-05  互联共商     Tags:ClickHouse   点击:(34)  评论:(0)  加入收藏
我们知道悲观锁在高并发的场景下,激烈的锁竞争会造成线程阻塞,大量阻塞线程会导致系统上下文切换,增加系统的性能开销。那么有没有可能实现一种非阻塞的锁机制来保证线程的安全...【详细内容】
2022-08-28  互联网资讯看板  网易  Tags:乐观锁   点击:(38)  评论:(0)  加入收藏
站内最新
站内热门
站内头条