【数据结构】堆-EW帮帮网

数组抽象维护成的完全二叉树结构是堆，堆中所有树的根节点都比其相邻子树根节点大(或小)，从上往下呈树型分叉递减(分次叉递次减)排列，其中最上层开始分叉的一个总节点是整个堆结构的最大值(或最小值)，出队列出优先级最高的数据即出堆结构最上层总节点即数组的0下标第一个元素

一、调整

调整过程

对堆进行向上调整或向下调整时，一定是一个待调整数据影响出了一个最小叉树非堆区域，在其调整路径关联的其它区域务必得是结构已好的堆区域给待调整数据进来比较下的，在最小叉树非堆区域里调整交换待调整数据位置使该非堆区域调整为堆区域，但同时待调整数据交换替换进入到别的原本堆区域，可能会破坏该区域原本的堆结构变成新的最小叉树非堆区域，如果该调整数据交换进来破坏了就要继续对它进行调整交换，直到它到新区域最终也能成为堆一部分为止(待调整数据到树底层或顶层时一定能调整好融入堆部分)，所以要对它一路检测一路调直到融入成堆为止

呈现结构

调整的整体结构呈一个最小叉树非堆区域往路径上的堆区域补好转移又流动着的

1.向下调整

—> 父往子向下去换着

调整有调整成小根堆的与大根堆的两方法，这里举例调整成小根堆的方法：

int child = (2*parent)+1：

由要向下调整的父节点得其左子节点

while (child < usedSize)、if(child+1 < usedSize)：

向下得大的子节点可能存在越数组界但防好了

2.向上调整

—> 子往父向上去换着

举例调整成小根堆的方法：

parent = (child - 1) / 2：

由要向上调整的子节点得到其父节点

while(child > 0)：

如果child路径上往父节点向上调过程中一直没有融入堆中，最后到总根节点child=0时是一定满足堆性质融进去的，如果到最后一次child = 0, parent = (0 - 1) / 2 = - 1/2 ，向上得父节点可能会出现下标小到负数，不过也已防好此时再上去会跳出循环不会越界的

二、创建

1.向下调整建堆

因为对待调整数据调整时其路径关联的区域必须得在已是堆结构下进行的，所以如果以向下调整所有数据来建堆时在下面倒数第二层第一个有父节点处开始建堆，因为此处调整的路径下面就是叶子节点不关联堆结构，可以调整建出堆结构，然后上层依次用刚建出的堆结构路径来向上全部父节点数据都调整完就把整体堆建好了：

usedSize - 1：定位到最后一个子节点

(usedSize - 1) / 2：下面倒数第二层第一个父节点

2.向上调整建堆

相同地，向上调整所有数据建堆时在第二层处第一个子节点开始建堆，然后依次往下在建好的堆结构路径下依次把所有的子节点数据都调整完就建好整体堆了：

我们一般采用向下调整建堆，因为与向上调整建堆相比，不用对最下层最多节点层的节点去调整数据而是多去对一层只有一个节点的去调整

三、插入

将数据插入到堆结构中，因为整体已经是全堆结构，所以全路径都已经是堆环境路径都可以去调的，数据插入时，将数据插入到最下层末尾节点处，对它一个数据进行一次向上调整，调整完一次就把此数据插入融入到堆中了

四、删除

堆的删除即实现出队列出最高优先级数据即出堆顶元素，将堆顶元素与最下层最后一个节点交换值，然后usedSize--，最后一个节点即堆顶的数据就删除了，然后对现刚换上来的堆顶数据进行向下调整一次就调整好了

五、应用

Top-k排序

1.升序建小堆

1.1前k个大的数据：

利用小堆显出最小数据，遍历一遍，数据比当前最小数据大就进去，最后堆维护出的就是所有数据中前k个大的数据

1.2第k个大的数据：

此时堆顶元素是所有数据中最大的数据，如果要取第k个大的数据，就再对堆删除k-1个元素即可得到

2.降序建大堆

2.1前k个小的数据：

利用大堆显出最大数据，遍历一遍，数据比当前最大数据小就进去，最后堆维护出的就是所有数据中前k个小的数据

2.2第k个小的数据：

此时堆顶元素是所有数据中的最小元素，如果要取第k个小的数据，就再对堆删除k-1个元素即可得到

六、PriorityQueue实现类

1.传比较器的构造方法

PriorityQueue优先级队列默认实现的是小根堆(o1 - o2)，如果要指定实现大小根堆，需要在构造时传入自己定义实现的比较器类的实例变量(大根堆o2 - o1)

2.比较器的补充

排序时，默认没有传入比较器的情况下，和优先级队列构造一样，都是默认以o1 - o2第一个参数减去第二个参数来计算返回的

假设o1为方法的第一个参数，o2为方法的第二个参数

当方法返回值小于0接收后，会将第一个参数排在前面，第二个参数排在后面
当返回值大于0时，会将第二个参数排在前面，第一个参数排在后面

所以，默认的o1 - o2 实现的是升序排列

【数据结构】堆

堆