【资料图】
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中文网其它相关文章！
