Java 數(shù)據(jù)結(jié)構(gòu)之堆的概念與應(yīng)用

更新時(shí)間：2021年10月18日 15:43:35 作者：文墨軒

堆是一顆完全二叉樹，在這棵樹中，所有父節(jié)點(diǎn)都滿足大于等于其子節(jié)點(diǎn)的堆叫大根堆，所有父節(jié)點(diǎn)都滿足小于等于其子節(jié)點(diǎn)的堆叫小根堆，堆雖然是一顆樹，但是通常存放在一個(gè)數(shù)組中，父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的父子關(guān)系通過數(shù)組下標(biāo)來確定

什么是堆

堆指的是使用數(shù)組保存完全二叉樹結(jié)構(gòu)，以層次遍歷的方式放入數(shù)組中。
如圖：

在這里插入圖片描述

注意：堆方式適合于完全二叉樹，對(duì)于非完全二叉樹若使用堆則會(huì)造成空間的浪費(fèi)
對(duì)于根節(jié)點(diǎn)與其左右孩子在數(shù)組中的下標(biāo)關(guān)系可表示為:left=2parent+1,right=2parent+2,parent=(child-1)/2

堆的類型

對(duì)于堆來說一共有兩種類型：一為大根堆，還有一個(gè)為小根堆

小根堆

小根堆指的是：所有的根結(jié)點(diǎn)的值小于左右孩子結(jié)點(diǎn)的值
如圖：

在這里插入圖片描述

大根堆

大根堆指的是：所有根結(jié)點(diǎn)的值大于左右孩子結(jié)點(diǎn)的值。
如圖：

在這里插入圖片描述

當(dāng)使用堆進(jìn)行從小到大進(jìn)行排序時(shí)應(yīng)該使用大堆進(jìn)行排序

堆的基本操作：創(chuàng)建堆

以創(chuàng)建大堆為例：我們先給定一個(gè)數(shù)組，該數(shù)組在邏輯上可以視為一顆完全二叉樹，但目前并不是堆，但我們可以通過一定的算法將其變化為堆，通常我們從倒數(shù)第一個(gè)結(jié)點(diǎn)進(jìn)行調(diào)整，一直調(diào)整到根結(jié)點(diǎn)的數(shù)，這樣就調(diào)整為堆了；
如示例：

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

調(diào)整方式：
第一步：先將數(shù)組還原成一個(gè)完全二叉樹
如圖：

在這里插入圖片描述

第二步：如果倒數(shù)第一個(gè)葉子結(jié)點(diǎn)有兄弟結(jié)點(diǎn)則先與兄弟結(jié)點(diǎn)比較大小然后再取大的結(jié)點(diǎn)與父結(jié)點(diǎn)比較大小，如果沒有兄弟結(jié)點(diǎn)則直接與父結(jié)點(diǎn)比較大小，如果值比父結(jié)點(diǎn)值大則交換值，一直這樣調(diào)整到根節(jié)點(diǎn)的樹，就可以調(diào)整成堆。
操作如圖：

在這里插入圖片描述

其核心代碼如下：

 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));
    }

在這里插入圖片描述

堆的時(shí)間復(fù)雜度和空間復(fù)雜度

建堆時(shí)沒有使用額外的空間因此其空間復(fù)雜度為O(1);
注意：該函數(shù)shiftDown（int[] array,int parent)時(shí)間復(fù)雜度為O(logn),建堆的時(shí)間復(fù)雜度為O(n*logn),但是建堆的時(shí)間復(fù)雜度為O(n)其推導(dǎo)如下：

在這里插入圖片描述

堆的應(yīng)用-優(yōu)先級(jí)隊(duì)列

概念

我們通常需要按照優(yōu)先級(jí)情況對(duì)待處理對(duì)象進(jìn)行處理，比如首先處理優(yōu)先級(jí)最高的對(duì)象，然后處理次高的對(duì)象.一個(gè)簡單的例子：一天晚上，你正在看電視，這時(shí)你的父母叫你去廚房幫忙，那么這時(shí)你應(yīng)該處理最重要的事情：去廚房幫媽媽的忙在這種情況下，我們的數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個(gè)最基本的操作，一個(gè)是返回最高優(yōu)先級(jí)對(duì)象，一個(gè)是添加新的對(duì)象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級(jí)隊(duì)列(Priority Queue)。
注意：實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方式有很多種，一般來說我們一般使用堆來構(gòu)建優(yōu)先級(jí)隊(duì)列

優(yōu)先級(jí)隊(duì)列基本操作

入優(yōu)先級(jí)隊(duì)列

以大堆為例：

首先按尾插方式放入數(shù)組
比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質(zhì)，插入結(jié)束
否則，交換其和雙親位置的值，重新進(jìn)行 2、3 步驟
直到根結(jié)點(diǎn)

如圖：

在這里插入圖片描述

核心代碼如下：

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

    public TestHeap() {
        this.elem = new int[10];//先創(chuàng)建長度為10的數(shù)組
    }
    public  boolean isFull() {
        return this.usedSize == this.elem.length;
    }
    public void push(int val) {
    //先判斷隊(duì)列是否已經(jīng)滿，如果以滿則擴(kuò)容
        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;
            }
        }
    }
    
}

出優(yōu)先級(jí)隊(duì)列首元素

注意：為了防止破壞堆的結(jié)構(gòu)，刪除時(shí)并不是直接將堆頂元素刪除，而是用數(shù)組的最后一個(gè)元素替換堆頂元素，然后通過向
下調(diào)整方式重新調(diào)整成堆

核心代碼如下：

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

    public TestHeap() {
        this.elem = new int[10];//10個(gè)0
    }
    public  boolean isFull() {
        return this.usedSize == this.elem.length;
    }
    public  boolean isEmpty() {
        return this.usedSize == 0;
    }
    public int poll() {
        //先判斷隊(duì)列是否為空，如果為空則拋出異常
        if (isEmpty()){
            throw new RuntimeException("優(yōu)先級(jí)隊(duì)列為空");
        }
        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;
        //進(jìn)入這個(gè)循環(huán) 說明最起碼你有左孩子
        while (child < this.usedSize) {
        	//該條件進(jìn)入是判斷其是否有右兄弟
            if(child+1 < this.usedSize &&
             this.elem[child] < this.elem[child+1]) {
                child++;
            }
            //child所保存的下標(biāo)，就是左右孩子的最大值
            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;//如果孩子節(jié)點(diǎn)比父親節(jié)點(diǎn)小 直接結(jié)束了
            }
        }
    }
}

java的優(yōu)先級(jí)隊(duì)列

在java中，我們不必單獨(dú)創(chuàng)建一個(gè)堆用于實(shí)現(xiàn)優(yōu)先級(jí)對(duì)列
可以使用PriorityQueue
例如：

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

java中的優(yōu)先級(jí)對(duì)列其實(shí)是小堆若想使用大堆方法則需要從寫比較方法
方法如下（方法不唯一）

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

優(yōu)先級(jí)的使用方法：

錯(cuò)誤處理	拋出異常	返回特殊值
入隊(duì)列	add(e)	offer(e)
出隊(duì)列	remove()	poll()
隊(duì)首元素	element()	peek()

堆的常見面試題

最后一塊石頭的重量

最后一塊石頭的重量題

在這里插入圖片描述

解題思路：該題可以使用變化過的優(yōu)先級(jí)隊(duì)列進(jìn)行解答，即將默認(rèn)小堆的優(yōu)先級(jí)隊(duì)列改為大堆模式的優(yōu)先級(jí)隊(duì)列，則將每塊石塊的重量使用循環(huán)放入優(yōu)先級(jí)隊(duì)列中其自動(dòng)會(huì)把最重的石塊放入隊(duì)首，而后，將隊(duì)列的頭兩個(gè)元素依次取出記為max1,max2,并將sum=max1-max2;如果sum大于0則又放入隊(duì)列中不是則繼續(xù)重復(fù)上訴操作

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個(gè)最接近的元素

在這里插入圖片描述

題解主要思路：使用優(yōu)先級(jí)隊(duì)列，先判別k是否大于數(shù)組長度，大于則直接將數(shù)組存放到List，相反則先依次存放k個(gè)數(shù)，之后將想要存放到優(yōu)先級(jí)隊(duì)列中的數(shù)-x的絕對(duì)值記為sum1,隊(duì)列中第一個(gè)元素-x的絕對(duì)值記為sum2，如果sum1小于sum2則將隊(duì)列中第一個(gè)元素刪除，將其他數(shù)放入隊(duì)列中，最后將隊(duì)列中元素存放到list中

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) {
                list.add(num);
            }
        }
        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()){
                list.add(queue.poll());
            }
        }
        return list;
    }
}

在這里插入圖片描述

查找和最小的K對(duì)數(shù)字

在這里插入圖片描述

主體解題思路：使用優(yōu)先級(jí)隊(duì)列將其先改變?yōu)榇蠖涯Ｊ?，使用循環(huán)先存放k個(gè)元素，之后想要存入隊(duì)列的元素與隊(duì)頭元素比較，如果比隊(duì)頭元素小則刪除隊(duì)頭元素，存放該元素，相反則繼續(xù)上訴操作最后放入數(shù)組中

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){
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    queue.offer(list);
                }
                else {
                    int tmp=queue.peek().get(0)+queue.peek().get(1);
                    if(nums1[i]+nums2[j]<tmp){
                        queue.poll();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        queue.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> list=new ArrayList<>();
        for (int i = 0; i < k&&!queue.isEmpty(); i++) {
            list.add(queue.poll());
        }
        return list;
    }
}

在這里插入圖片描述

到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)之堆的概念與應(yīng)用的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: