>首页> IT >

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

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


【资料图】

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

推荐学习:《java视频教程》

一、前言

堆的历史

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

二、堆的数据结构

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

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

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

三、堆的代码实现

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举例,如图所示入堆过程。

首先将元素2挂到队列尾部,之后通过 (k - 1) >>> 1 计算父节点位置,与对应元素进行比对和判断交换。

交换过程包括 2->6、2->5,以此交换结束后元素保存完毕。

3. 出堆实现

元素的出堆其实很简单,只要把根元素直接删除弹出即可。但剩余接下里的步骤才是复杂的,因为需要在根元素迁移走后,寻找另外的最小元素迁移到对头。这个过程与入堆正好相反,这是一个不断向下迁移的过程。

private void siftDownComparable(int k, E x) {    // 先找出中间件节点    int half = size >>> 1;    while (k < half) {        // 找到左子节点和右子节点,两个节点进行比较,找出最大的值        int child = (k << 1) + 1;        Object c = queue[child];        int right = child + 1;        // 左子节点与右子节点比较,取最小的节点        if (right < size && compareTo((E) c, (E) queue[right]) > 0) {            logger.info("【出队】左右子节点比对,获取最小值。left:{} right:{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));            c = queue[child = right];        }        // 目标值与c比较,当目标值小于c值,退出循环。说明此时目标值所在位置适合,迁移完成。        if (compareTo(x, (E) c) <= 0) {            break;        }        // 目标值小于c值,位置替换,继续比较        logger.info("【出队】替换过程,节点的值比对。上节点:{} 下节点:{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));        queue[k] = c;        k = child;    }    // 把目标值放到对应位置    logger.info("【出队】替换结果,最终更换位置。Idx:{} Val:{}", k, JSON.toJSONString(x));    queue[k] = x;}

不断地向下迁移元素。这个过程会比对左右子节点的值,找到最小的。所以整个过程会比入堆麻烦一些。

这里以弹出元素1举例,之后将堆尾元素替换到相应的位置。整个过程分为6张图表述。

图1到图2,找出根元素弹出。图3到图4,将根元素向下迁移,与子元素比对,并替换位置。如果这个位置与8相比,小于8则继续向下迁移。图4到图5,继续迁移,在原节点4的位置对应的两个子元素,都比8大,这个时候就可以停下来了。图5到图6,更换元素位置,把队尾的元素替换到对应元素1向下迁移检测的位置。

4. 小堆实现

小堆是一个正序比对

public class MinHeap extends Heap {    @Override    public int compareTo(Integer firstElement, Integer secondElement) {        return firstElement.compareTo(secondElement);    }}

测试

@Testpublic void test_min_heap() {    MinHeap heap = new MinHeap();    // 存入元素    heap.add(1);    heap.add(3);    heap.add(5);    heap.add(11);    heap.add(4);    heap.add(6);    heap.add(7);    heap.add(12);    heap.add(15);    heap.add(10);    heap.add(9);    heap.add(8);    // 弹出元素    while (heap.peek() != null){        logger.info("测试结果:{}", heap.poll());    }}

结果

小堆就是一个正序的输出结果,从小到大的排序和输出。小堆空间:[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

5. 大堆实现

小堆是一个反序比对

public class MaxHeap extends Heap {    @Override    public int compareTo(Integer firstElement, Integer secondElement) {        return secondElement.compareTo(firstElement);    }}

测试

@Testpublic void test_max_heap() {    MaxHeap heap = new MaxHeap();    // 存入元素    heap.add(1);    heap.add(3);    heap.add(5);    heap.add(11);    heap.add(4);    heap.add(6);    heap.add(7);    heap.add(12);    heap.add(15);    heap.add(10);    heap.add(9);    heap.add(8);    // 弹出元素    while (heap.peek() != null){        logger.info("测试结果:{}", heap.poll());    }}

结果

大堆就是一个反序的输出结果,从大到小的排序和输出。

大堆空间:[15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null,null,null,null,null]

推荐学习:《java视频教程》

以上就是Java数据结构之最小堆和最大堆的原理及实现详解的详细内容,更多请关注php中文网其它相关文章!

关键词: 数据结构 当前位置 就是一个