Java數(shù)據(jù)結(jié)構(gòu)之堆怎么建立

今天小編給大家分享一下Java數(shù)據(jù)結(jié)構(gòu)之堆怎么建立的相關(guān)知識點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

堆的性質(zhì)

堆邏輯上是一棵完全二叉樹，堆物理上是保存在數(shù)組中 。

總結(jié)：一顆完全二叉樹以層序遍歷方式放入數(shù)組中存儲，這種方式的主要用法就是堆的表示。

并且 如果已知父親(parent) 的下標(biāo)，

則： 左孩子(left) 下標(biāo) = 2 * parent + 1;

右孩子(right) 下標(biāo) = 2 * parent + 2;

已知孩子（不區(qū)分左右）(child)下標(biāo)，則：

雙親(parent) 下標(biāo) = (child - 1) / 2;

堆的分類

大堆：根節(jié)點(diǎn)大于左右兩個(gè)子節(jié)點(diǎn)的完全二叉樹 （父親節(jié)點(diǎn)大于其子節(jié)點(diǎn)），叫做大堆，或者大根堆，或者最大堆 。

小堆：根節(jié)點(diǎn)小于左右兩個(gè)子節(jié)點(diǎn)的完全二叉樹叫 小堆（父親節(jié)點(diǎn)小于其子節(jié)點(diǎn)），或者小根堆，或者最小堆。

堆的向下調(diào)整

現(xiàn)在有一個(gè)數(shù)組，邏輯上是完全二叉樹，我們通過從根節(jié)點(diǎn)開始的向下調(diào)整算法可以把它調(diào)整成一個(gè)小堆或者大堆。向下調(diào)整算法有一個(gè)前提：左右子樹必須是一個(gè)堆，才能調(diào)整。

以小堆為例：

1、先讓左右孩子結(jié)點(diǎn)比較，取最小值。

2、用較小的那個(gè)孩子結(jié)點(diǎn)與父親節(jié)點(diǎn)比較，如果孩子結(jié)點(diǎn)<父親節(jié)點(diǎn)，交換，反之，不交換。

3、循環(huán)往復(fù)，如果孩子結(jié)點(diǎn)的下標(biāo)越界，則說明已經(jīng)到了最后，就結(jié)束。

代碼示例：

 //parent: 每棵樹的根節(jié)點(diǎn)
 //len: 每棵樹的調(diào)整的結(jié)束位置
public void shiftDown(int parent,int len){
        int child=parent*2+1; //因?yàn)槎咽峭耆鏄洌瑳]有左孩子就一定沒有右孩子，所以最起碼是有左孩子的，至少有1個(gè)孩子
        while(child<len){
            if(child+1<len && elem[child]<elem[child+1]){
                child++;//兩孩子結(jié)點(diǎn)比較取較小值
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

堆的建立

給出一個(gè)數(shù)組，這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個(gè)堆（左右子樹不滿足都是大堆或者小堆），現(xiàn)在我們通過算法，把它構(gòu)建成一個(gè)堆（大堆或者小堆）。該怎么做呢？這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹開始調(diào)整，一直調(diào)整到根節(jié)點(diǎn)的樹，就可以調(diào)整成堆。 這里我們就要用到剛才寫的向下調(diào)整。

public void creatHeap(int[] arr){
        for(int i=0;i<arr.length;i++){
            elem[i]=arr[i];
            useSize++;
        }
        for(int parent=(useSize-1-1)/2;parent>=0;parent--){//數(shù)組下標(biāo)從0開始
            shiftDown(parent,useSize);
        }
    }

建堆的空間復(fù)雜度為O（N），因?yàn)槎褳橐豢猛耆鏄洌瑵M二叉樹也是一種完全二叉樹，我們用滿二叉樹（最壞情況下）來證明。

堆得向上調(diào)整

現(xiàn)在有一個(gè)堆，我們需要在堆的末尾插入數(shù)據(jù)，再對其進(jìn)行調(diào)整，使其仍然保持堆的結(jié)構(gòu)，這就是向上調(diào)整。

以大堆為例：

代碼示例：

public void shiftup(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

堆的常用操作

入隊(duì)列

往堆里面加入元素，就是往最后一個(gè)位置加入，然后在進(jìn)行向上調(diào)整。

public boolean isFull(){
        return elem.length==useSize;
    }
public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);//擴(kuò)容
        }
        elem[useSize++]=val;
        shiftup(useSize-1);
    }

出隊(duì)列

把堆里元素刪除，就把堆頂元素和最后一個(gè)元素交換，然后向整個(gè)數(shù)組大小減一，最后向下調(diào)整，就刪除了棧頂元素。

public boolean isEmpty(){
        return useSize==0;
    }
public int poll(){
        if(isEmpty()){
            throw new RuntimeException("優(yōu)先級隊(duì)列為空");
        }
        int tmp=elem[0];
        elem[0]=elem[useSize-1];
        elem[useSize-1]=tmp;
        useSize--;
        shiftDown(0,useSize);
        return tmp;
    }

獲取隊(duì)首元素

public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("優(yōu)先級隊(duì)列為空");
        }
        return elem[0];
    }

TopK 問題

給你6個(gè)數(shù)據(jù)，求前3個(gè)最大數(shù)據(jù)。這時(shí)候我們用堆怎么做的？

解題思路：

1、如果求前K個(gè)最大的元素，要建一個(gè)小根堆。

2、如果求前K個(gè)最小的元素,要建一個(gè)大根堆。

3、第K大的元素。建一個(gè)小堆,堆頂元素就是第K大的元素。

4、第K小的元素。建一個(gè)大堆,堆頂元素就是第K大的元素。

例子

舉個(gè)例子：求前n個(gè)最大數(shù)據(jù)

代碼示例：

 public static int[] topK(int[] array,int k){
        //創(chuàng)建一個(gè)大小為K的小根堆
        PriorityQueue<Integer> minHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        //遍歷數(shù)組中元素，將前k個(gè)元素放入隊(duì)列中
        for(int i=0;i<array.length;i++){
            if(minHeap.size()<k){
                minHeap.offer(array[i]);
            }else{
                //從k+1個(gè)元素開始，分別和堆頂元素比較
                int top=minHeap.peek();
                if(array[i]>top){
                    //先彈出后存入
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        //將堆中元素放入數(shù)組中
        int[] tmp=new int[k];
        for(int i=0;i< tmp.length;i++){
            int top=minHeap.poll();
            tmp[i]=top;
        }
        return tmp;
    }
    public static void main(String[] args) {
        int[] array={12,8,23,6,35,22};
        int[] tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

結(jié)果：

數(shù)組排序

再者說如果要對一個(gè)數(shù)組進(jìn)行從小到大排序，要借助大根堆還是小根堆呢？

---->大根堆

代碼示例：

  public void heapSort(){
        int end=useSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);//假設(shè)這里向下調(diào)整為大根堆
            end--;
        }
    }

以上就是“Java數(shù)據(jù)結(jié)構(gòu)之堆怎么建立”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。