java数据结构的堆

## 堆的基本操作：创建堆

//建堆前
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<array.length){
if(child+1<array.length){
if (array[child]<array[child+1]){
child++;
}
}
if(array[child]>array[parent]){
int tmp=array[child];
array[child]=array[parent];
array[parent]=tmp;
parent=child;
child=parent*2+1;
}
else {
break;
}
}
}
public static void createHeap(int[] array){
for (int i = (array.length-1-1)/2; i >=0; i--) {
shiftDown(array,i);
}
}
public static void main(String[] args) {
int array[]={1,5,3,8,7,6};
createHeap(array);
System.out.println(Arrays.toString(array));
}

## 堆的应用-优先级队列

### 优先级队列基本操作

#### 入优先级队列

• 首先按尾插方式放入数组
• 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
• 否则，交换其和双亲位置的值，重新进行 2、3 步骤
• 直到根结点

public class TestHeap {
public int[] elem;
public int usedSize;

public TestHeap() {
this.elem = new int[10];//先创建长度为10的数组
}
public  boolean isFull() {
return this.usedSize == this.elem.length;
}
public void push(int val) {
//先判断队列是否已经满，如果以满则扩容
if (isFull()){
Arrays.copyOf(this.elem,this.elem.length*2);
}
this.elem[this.usedSize++]=val;
shiftUp(this.usedSize-1);
}
public void shiftUp(int child) {
int parent=(child-1)/2;
while (parent>=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的优先级队列

PriorityQueue<Integer> queue=new PriorityQueue<>();

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

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

### 堆的常见面试题

#### 最后一块石头的重量

class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);//改为大堆
for(int i=0;i<stones.length;i++){
queue.offer(stones[i]);
}
while(queue.size()>=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个最接近的元素

class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
PriorityQueue<Integer> queue=new PriorityQueue<>();
List<Integer> list=new ArrayList<>();
if(k>arr.length){
for (int num:arr) {
}
}
else {
for (int i = 0; i < arr.length; i++) {
if(i<k){
queue.offer(arr[i]);
}
else {
int sum1=Math.abs(arr[i]-x);
int sum2=Math.abs(queue.peek()-x);
if(sum1<sum2){
queue.poll();
queue.offer(arr[i]);
}
}
}
while (!queue.isEmpty()){
}
}
return list;
}
}

#### 查找和最小的K对数字

class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<List<Integer>> queue=new PriorityQueue<>(k,(o1,o2)->{
return o2.get(0)+o2.get(1)-o1.get(0)-o1.get(1);
});
for (int i=0;i<Math.min(nums1.length,k);i++)
{
for (int j = 0; j < Math.min(nums2.length, k); j++) {
List<Integer> list=new ArrayList<>();
if (queue.size()<k){
queue.offer(list);
}
else {
int tmp=queue.peek().get(0)+queue.peek().get(1);
if(nums1[i]+nums2[j]<tmp){
queue.poll();
queue.offer(list);
}
}
}
}
List<List<Integer>> list=new ArrayList<>();
for (int i = 0; i < k&&!queue.isEmpty(); i++) {