Shulou(Shulou.com)06/03 Report--

This article is about what is useful in Java. Xiaobian thinks it is quite practical, so share it with everyone for reference. Let's follow Xiaobian and have a look.

What's a pile?

Heap refers to the use of arrays to store a complete binary tree structure, placed in an array in a hierarchical traversal manner.

As shown in the figure:

Note: heap mode is suitable for complete binary tree, for incomplete binary tree if the use of heap will cause space waste

The subscript relationship between the root node and its left and right children in the array can be expressed as:left=2parent+1,right=2parent+2,parent=(child-1)/2

Type of heap

There are two types of heaps: one with large roots and one with small roots

Xiaogendui

A small root heap means that the values of all root nodes are less than the values of the left and right child nodes

As shown in the figure:

Dagendui

A large root heap means that all root nodes have values greater than the values of the left and right child nodes.

As shown in the figure:

当使用堆进行从小到大进行排序时应该使用大堆进行排序

堆的基本操作：创建堆

以创建大堆为例：我们先给定一个数组，该数组在逻辑上可以视为一颗完全二叉树，但目前并不是堆，但我们可以通过一定的算法将其变化为堆，通常我们从倒数第一个结点进行调整，一直调整到根结点的数，这样就调整为堆了;

如示例：

//建堆前int array[]={1,5,3,8,7,6};//建堆后int array[]={ 8,7,6,5,1,3 };

调整方式：

第一步：先将数组还原成一个完全二叉树

如图：

第二步：如果倒数第一个叶子结点有兄弟结点则先与兄弟结点比较大小然后再取大的结点与父结点比较大小，如果没有兄弟结点则直接与父结点比较大小，如果值比父结点值大则交换值，一直这样调整到根节点的树，就可以调整成堆。

操作如图：

其核心代码如下：

public static void shiftDown(int[] array,int parent){ int child=2*parent+1; while (child=0){ if(this.elem[child]>this.elem[parent]){ int tmp=this.elem[child]; this.elem[child]=this.elem[parent]; this.elem[parent]=tmp; child=parent; parent=(child-1)/2; } else{ break; } } } }出优先级队列首元素

注意：为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向

下调整方式重新调整成堆

核心代码如下：

public class TestHeap { public int[] elem; public int usedSize; public TestHeap() { this.elem = new int[10];//10个0 } public boolean isFull() { return this.usedSize == this.elem.length; } public boolean isEmpty() { return this.usedSize == 0; } public int poll() { //先判断队列是否为空，如果为空则抛出异常 if (isEmpty()){ throw new RuntimeException("优先级队列为空"); } int tmp=this.elem[0]; this.elem[0]=this.elem[this.usedSize-1]; this.usedSize--; shiftDown(0); return tmp; } public void shiftDown(int parent) { int child = 2*parent+1; //进入这个循环 说明最起码你有左孩子 while (child

< this.usedSize) { //该条件进入是判断其是否有右兄弟 if(child+1 < this.usedSize && this.elem[child] < this.elem[child+1]) { child++; } //child所保存的下标，就是左右孩子的最大值 if(this.elem[child] >

this.elem[parent]) { int tmp = this.elem[child]; this.elem[child] = this.elem[parent]; this.elem[parent] = tmp; parent = child; child = 2*parent+1; }else { break;//如果孩子节点比父亲节点小 直接结束了 } } }}java的优先级队列

在java中，我们不必单独创建一个堆用于实现优先级对列

可以使用PriorityQueue

例如：

PriorityQueue queue=new PriorityQueue();

java中的优先级对列其实是小堆若想使用大堆方法则需要从写比较方法

方法如下（方法不唯一）

PriorityQueue queue=new PriorityQueue(new Comparator(Integer)){public int compare(Integer o1,Integer o2){return o2-o1}};

优先级的使用方法：

错误处理抛出异常返回特殊值入队列add(e)offer(e)出队列remove()poll()队首元素element()peek()堆的常见面试题最后一块石头的重量

最后一块石头的重量题

解题思路：该题可以使用变化过的优先级队列进行解答，即将默认小堆的优先级队列改为大堆模式的优先级队列，则将每块石块的重量使用循环放入优先级队列中其自动会把最重的石块放入队首，而后，将队列的头两个元素依次取出记为max1,max2,并将sum=max1-max2;如果sum大于0则又放入队列中不是则继续重复上诉操作

class Solution { public int lastStoneWeight(int[] stones) {PriorityQueue queue = new PriorityQueue((i1, i2) -> i2 - i1);//改为大堆 for(int i=0;i=2){ int max1=queue.poll(); int max2=queue.poll(); int sum=max1-max2; if(sum>0){ queue.offer(sum); } } if(queue.size()>0){ return queue.poll(); } return 0; }}

找到K个最接近的元素

找到K个最接近的元素

题解主要思路：使用优先级队列，先判别k是否大于数组长度，大于则直接将数组存放到List，相反则先依次存放k个数，之后将想要存放到优先级队列中的数-x的绝对值记为sum1,队列中第一个元素-x的绝对值记为sum2，如果sum1小于sum2则将队列中第一个元素删除，将其他数放入队列中，最后将队列中元素存放到list中

class Solution { public List findClosestElements(int[] arr, int k, int x) { PriorityQueue queue=new PriorityQueue(); List list=new ArrayList(); if(k>arr.length){ for (int num:arr) { list.add(num); } } else { for (int i = 0; i < arr.length; i++) { if(i

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.