Java数据结构之最小堆和最大堆的原理及实现详解

本篇文章给大家带来了关于java的相关知识,在计算机科学中,堆(heap) 的实现是一种基于树的特殊的数据结构,它可以在数组上构建出树的结构体,并满足堆的属性,下面就来聊聊Java数据结构中的堆,感兴趣的可以了解一下。

Java数据结构之最小堆和最大堆的原理及实现详解

java代码一键生成、拖拽设计:立即使用

一、前言

堆的历史

堆的数据结构有很多种体现形式,包括;2-3堆、B堆、斐波那契堆,而在 Java API 中最常用的是用于实现优先队列的二叉堆,它是由 JWJ Williams 在 1964 年引入的,作为堆排序算法的数据结构。另外在 Dijkstra 算法等几种高效的图算法中,堆也是非常重要的。

二、堆的数据结构

在计算机科学中,堆(heap) 的实现是一种基于树的特殊的数据结构,它可以在数组上构建出树的结构体,并满足堆的属性;

最小堆:如果P 是C 的一个父级节点, 那么P 的key(或value)应小于或等于C 的对应值。

Java数据结构之最小堆和最大堆的原理及实现详解

最大堆:与最小堆的定义正好相反,最大堆(max heap) ,P 的key(或value)大于C 的对应值。

Java数据结构之最小堆和最大堆的原理及实现详解

三、堆的代码实现

1. 实现介绍

堆的实现在 Java API 中主要体现在延迟队列的实现二叉堆上,这里小傅哥单独把这部分代码拆分出来,了解下关于小堆和大堆的实现。

从对堆的数据结构介绍上可以看到,小堆和大堆的唯一区别仅是对元素的排序方式不同。所以也就是说在存放和获取元素的时候对元素的填充和摘除时,排序方式不同而已。

2. 入堆实现

堆的在存放元素时,以遵循它的特点,会在存放过程中,通过队尾元素向上比对迁移。

private void siftUpComparable(int k, E x) {
    logger.info("【入队】元素:{} 当前队列:{}", JSON.toJSONString(x), JSON.toJSONString(queue));
    while (k > 0) {
        // 获取父节点Idx,相当于除以2
        int parent = (k - 1) >>> 1;
        logger.info("【入队】寻找当前节点的父节点位置。k:{} parent:{}", k, parent);
        Object e = queue[parent];
        // 如果当前位置元素,大于父节点元素,则退出循环
        if (compareTo(x, (E) e) >= 0) {
            logger.info("【入队】值比对,父节点:{} 目标节点:{}", JSON.toJSONString(e), JSON.toJSONString(x));
            break;
        }
        // 相反父节点位置大于当前位置元素,则进行替换
        logger.info("【入队】替换过程,父子节点位置替换,继续循环。父节点值:{} 存放到位置:{}", JSON.toJSONString(e), k);
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
    logger.info("【入队】完成 Idx:{} Val:{} \r\n当前队列:{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue));
}

入堆的实现 add 方法最终会调用到 siftUpComparable 方法,进行排序的方式进行处理。而这个排序 compareTo 方法是由具体的 MinHeap、MaxHeap 来做实现。

以入堆元素2举例,如图所示入堆过程。

Java数据结构之最小堆和最大堆的原理及实现详解

郑重声明:本文版权包含图片归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们(delete@yzlfxy.com)修改或删除,多谢。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

留言与评论(共有 0 条评论)
昵称:
匿名发表
   
验证码: