Java 最大堆,最小生成堆

　　这篇文章给你带来了一些关于java的知识。在计算机科学中，堆的实现是一种基于树的特殊数据结构，可以在数组上构建树结构，满足堆的属性。先说Java数据结构中的堆，有兴趣的可以了解一下。

　　如何解决写爬虫IP受阻的问题？立即使用。

一、前言

　　堆的历史记录

　　堆的数据结构有很多种形式，包括：2-3堆、B堆、Fibonacci堆，Java API中最常用的是用来实现优先级队列的二进制堆，它是由JWJ威廉姆斯在1964年提出的，作为堆排序算法的数据结构。另外，在Dijkstra算法等几种高效的图算法中，堆也是非常重要的。

二、堆的数据结构

　　在计算机科学中，堆的实现是一种基于树的特殊数据结构，可以在数组上构建树结构，满足堆的性质；

　　最小堆：如果P是C的父节点，那么P的键(或值)应该小于或等于C的对应值。

　　最大堆：与最小堆的定义相反，最大堆，p的键(或值)大于c的对应值。

三、堆的代码实现

1. 实现介绍

　　堆的实现主要体现在Java API中延迟队列的二进制堆。在这里，富哥单独拆分这部分代码，了解一下小堆和大堆的实现。

　　从堆的数据结构介绍可以看出，小堆和大堆唯一的区别就是元素的排序方式。也就是说，当元素被存储和检索时，它们以不同的方式被填充和移除。

2. 入堆实现

　　 heap，为了在存储元素时遵循其特性，在存储过程中会通过尾部元素进行迁移。

　　private void siftup comparable(int k，E x) {

　　Logger.info ([enqueue]元素：{}当前队列：{} ，json.tojsonstring (x)，JSON . tojsonstring(queue))；

　　while (k 0) {

　　//获取父节点Idx，相当于除以2

　　int parent=(k-1)1；

　　Logger.info ([enqueue])查找当前节点的父节点位置。k:{} parent:{} ，k，parent)；

　　object e=queue[parent]；

　　//如果当前位置元素大于父节点元素，则退出循环。

　　if (compareTo(x，(E) e)=0) {

　　Logger.info (enqueue 值比较，父节点：{}目标节点：{} ，json.tojsonstring (e)，JSON . tojsonstring(x))；

　　打破；

　　}

　　//反之，如果父节点位置大于当前位置元素，则替换它。

　　Logger.info ([enqueue]替换过程，父子节点位置被替换，循环继续。父节点值：{}存储在位置：{} ，JSON.toJSONString(e)，k)；

　　queue[k]=e；

　　k=父母；

　　}

　　queue[k]=x；

　　Logger.info ([enqueue]完成idx:{ } val:{} \ r \ n当前队列：{ } \ r \ n ，k，json.tojsonstring (x)，JSON . tojsonstring(queue))；

　　}堆中的实现add方法最终会调用siftupcability方法，对其进行排序和处理。而这个sort compareTo方法是通过具体的MinHeap和MaxHeap实现的。

　　以打桩元件2为例，打桩过程如图所示。

　　首先将元素2挂在队列末尾，然后通过(k-1) 1计算父节点位置，并与对应的元素进行比较判断。

　　交换过程包括2-6和2-5，以便在交换后保存元素。

3. 出堆实现

　　元素的解包其实很简单，直接删除根元素，弹出即可。但是剩下的步骤就复杂了，因为根元素迁移走之后，还需要寻找另一个最小的元素迁移到正确的元素上。这个过程正好与打桩相反，是一个不断向下迁移的过程。

　　private void sift down comparable(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 ([dequeue])比较左右两个子节点以获得最小值。left:{} right:{} ，JSON.toJSONString(c)，JSON . tojsonstring(queue[right])；

　　c=队列[child=right]；

　　}

　　//将目标值与C进行比较，当目标值小于C时，退出循环。此时，目标值的位置合适，迁移完成。

　　if (compareTo(x，(E) c)=0) {

　　打破；

　　}

　　//目标值小于C值，位置被替换，比较继续。

　　Logger.info ([dequeue]替换过程，比较节点的值。上层节点：{}下层节点：{}位置替换，json.tojsonstring (queue [k])，JSON . tojsonstring(c))；

　　queue[k]=c；

　　k=孩子；

　　}

　　//将目标值放在相应的位置

　　logger . info([出列]替换结果和最终替换位置。Idx:{} Val:{} ，k，JSON . tojsonstring(x))；

　　queue[k]=x；

　　}不断向下迁移元素。该过程将比较左右子节点的值，以找到最小的一个。所以整个过程会比打桩更麻烦。

　　以弹出元素1为例，然后用相应的位置替换尾部元素。整个过程分为六张图。

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

4. 小堆实现

　　小堆是一个正序比对

　　公共类MinHeap扩展HeapInteger {

　　@覆盖

　　public int compare to(Integer first element，Integer secondElement) {

　　返回first element . compare to(second element)；

　　}

　　}测试

　　@测试

　　public 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，空，空，空，空，空，空]:

5. 大堆实现

　　公共类MaxHeap扩展了HeapInteger {

　　@覆盖