1.堆（Heap）

1.1堆的概念

堆是一種非常重要的數(shù)據(jù)結構，通常被實現(xiàn)為一種特殊的完全二叉樹

如果有一個關鍵碼的集合K={k0,k1,k2,...,kn-1}，把它所有的元素按照完全二叉樹的順序存儲在一個一維數(shù)組中，如果滿足ki<=k2i+1且ki<=k2i+2(i=0,1,2,3...)，則稱這個集合為小堆；如果滿足ki>=k2i+1且ki>=k2i+2(i=0,1,2,3...)，則稱這個集合為大堆。

簡單來說，根節(jié)點的值為最大的堆叫做最大堆或大根堆，根節(jié)點的值最小的堆叫做最小堆或小根堆

1.2堆的性質

1.完全二叉樹的性質：

除了最后一層外，每一層都被填滿，最后一層的節(jié)點從左往后填充

2.堆序性質：

最大堆（大根堆）：

對于每個節(jié)點i，其左子節(jié)點2i+1和右子節(jié)點2i+2的值都小于或等于i的值

最小堆（小根堆）：

對于每個節(jié)點i，其左子節(jié)點2i+1和右子節(jié)點2i+2的值都大于或等于i的值

1.3堆的存儲方式

從堆的概念可知，堆是一顆完全二叉樹，因此可以以層序的規(guī)則方式來高效存儲

注意： 對于非完全二叉樹來說，不適合使用順序的方式進行存儲，因為為了還原二叉樹，空間中必須要存儲空節(jié)點，就會導致空間利用率比較低

1.4堆的創(chuàng)建

給定一個集合{28,16,20,19,29,35,66,50,26,38}，如何將其創(chuàng)建為堆呢？

觀察發(fā)現(xiàn)：根節(jié)點的左右子樹都已經(jīng)滿足堆的性質，因此只需要將根節(jié)點向下調整即可?

1.4.1堆的向下調整

1.用parent表示要調整的節(jié)點，child表示parent的左孩子（注意：堆是一顆完全二叉樹，如果parent有孩子一定是先有左孩子

2.如果parent的左孩子存在，即child<size，進行如下操作，直到parent的左孩子不存在：

? ? ? ?parent的右孩子是否存在，如果存在，則找到左右孩子中最小的元素，讓child表示這個元素。

? ? ? ?將parent與較小的孩子child進行比較，如果parent小于child，調整結束。

???????如果parent大于child，將parent和child進行交換，原來parent中較大的元素向下調整可能會導? ? ? ? ?致子樹不滿足堆的性質，因此要繼續(xù)向下調整，即parent=child，child=2*parent+1，繼續(xù)進? ? ? ? ? ?行步驟2

代碼編寫：

    public void shiftDown(int[] array,int parent){int child=2*parent+1;int size=array.length;while(child<size){//如果右孩子存在，用child標記左右孩子中較小的值if(child+1<size&&array[child+1]<array[child]){child++;}if(array[parent]>array[child]){swap(array,parent,child);//繼續(xù)向下調整，為了保證子樹也滿足堆的性質parent=child;child=2*parent+1;}else{break;}}}private void swap(int[] array,int a,int b){int tmp=array[a];array[a]=array[b];array[b]=tmp;}

?注意：再調整以parent為根的二叉樹時，必須滿足parent的左子樹和右子樹已經(jīng)時堆了才可以進行向下調整。

1.4.2堆的創(chuàng)建（小根堆）

那么對于普通的序列，即根節(jié)點的左右子樹不滿足堆的性質，又該如何創(chuàng)建呢？

例如對普通序列{2,7,8,5,4,1}進行小根堆的創(chuàng)建

根據(jù)上面的堆的向下調整，我們的思路就是要將根的左右子樹都滿足小根堆的特點，我們可以從下向上，從最后一個非葉子節(jié)點出發(fā)，將其與他們的左右孩子進行比較，將最小的值與非葉子節(jié)點進行交換（堆的向下調整），再繼續(xù)向上執(zhí)行上述操作，直到操作的節(jié)點為根節(jié)點即可

代碼編寫：

     public void createSmallestHeap(int [] array){int root=(array.length-2)>>1;for(;root>=0;root--){shiftDown(array,root);}}

?

1.5堆的插入和刪除

1.5.1堆的插入

堆的插入總共需要2步：

1.先將元素放入底層（空間不夠時，需要進行擴容）

2.將新插入的元素不斷向上調整，直到滿足堆的性質

觀察可以發(fā)現(xiàn)：如果新插入的節(jié)點的父節(jié)點大于新插入的節(jié)點，就進行元素的交換，不斷重復該動作

代碼編寫：

    //child表示新插入元素的索引public void shiftUp(int child){//找到新插入節(jié)點的父節(jié)點int parent=(child-1)/2;while(child>0){if(array[parent]>array[child]){swap(array,parent,child);child=parent;parent=(child-1)/2;}else {break;}}}

1.5.2堆的刪除

堆在刪除過程中需要注意刪除的元素一定是堆頂元素

1.將堆頂元素和堆中的左后一個元素交換位置

2.將堆中有效個數(shù)減少一個

3.對堆頂元素進行向下調整

代碼編寫：

     public void shiftDown(int[] array,int parent){int child=2*parent+1;int size=array.length;while(child<size){//如果右孩子存在，用child標記左右孩子中較小的值if(child+1<size&&array[child+1]<array[child]){child++;}if(array[parent]>array[child]){swap(array,parent,child);//繼續(xù)向下調整，為了保證子樹也滿足堆的性質parent=child;child=2*parent+1;}else{break;}}}public void delete(int[] array){swap(array,0,size-1);//size表示有效元素的個數(shù)size--;shiftDown(array,0);}

?

1.6堆的應用

1.堆排序（Heap Sort）

利用堆的性質對數(shù)組進行排序，時間復雜度為O(nlogn)

2.優(yōu)先級隊列（PriorityQueue）

堆是實現(xiàn)優(yōu)先級隊列的高校數(shù)據(jù)結構，支持快速的插入和刪除操作

3.Dijkstra算法

在最短路徑算法中，堆用于高效地選擇當前距離最小的節(jié)點

4.Kth Largest Element

也叫topK問題，使用堆可以高效地找到數(shù)組中的第k大元素

2.PriorityQueue

2.1什么是優(yōu)先級隊列

通過之前的介紹，隊列是一種先進先出(FIFO)的數(shù)據(jù)結構，但是優(yōu)先情況下，操作的數(shù)據(jù)可能帶有優(yōu)先級，并不希望按照隊列原始的順序進行出棧，可能優(yōu)先級高的元素想先出隊列

在生活中有一個很常見的例子：當你在用聽歌的時候，突然接到電話，音樂會自動停止，而執(zhí)行通話的操作

優(yōu)先級隊列（PriorityQueue）是一種特殊的隊列，其中的每個元素都有一個優(yōu)先級，隊列會根據(jù)優(yōu)先級來決定元素的出隊順序，優(yōu)先級高的元素先出隊，優(yōu)先級低的元素后出隊，如果兩個元素的優(yōu)先級相同，則按照它們入隊列的順序出隊

優(yōu)先級隊列通?；诙堰@種數(shù)據(jù)結構實現(xiàn)，因為堆可以高效地進行插入和刪除操作，同時保持元素的優(yōu)先級順序

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種類型的優(yōu)先級隊列，PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的，我們主要進行講解PriorityQueue

2.2PriorityQueue常見操作

PriorityQueue的常見方法：

方法	解釋
PriorityQueue()	創(chuàng)建一個空的優(yōu)先級隊列，默認容量是11
PriorityQueue(int initialCapacity)	創(chuàng)建一個初始容量為initialCapacity的優(yōu)先級隊列，注意：initialCapacity不能小于1，否則會拋出IllegalArgumentException異常
PriorityQueue(Collection<? extends E> c)	用一個集合來創(chuàng)建優(yōu)先級隊列
boolean offer(E e)	插入元素e，插入成功返回true，如果e對象為空，則會拋出NullPointerException異常，空間不夠的時候會進行擴容
E peek()	獲取優(yōu)先級最高的元素，如果優(yōu)先級隊列為空，返回null
E poll()	移除優(yōu)先級最高的元素，如果優(yōu)先級隊列為空，返回null
int size()	獲取有效元素的個數(shù)
void clear()	清空隊列
boolean isEmpty()	檢測優(yōu)先級隊列是否為空，如果為空返回true

?我們以一個復雜的類型來演示：

public class Student implements Comparable<Student>{private String name;private int age;public Student() {}public Student(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic int compareTo(Student o) {return this.age-o.age;}
}public class Test {public static void main(String[] args) {PriorityQueue<Student> queue=new PriorityQueue<>();Student s1=new Student("hajimi",21);Student s2=new Student("king",18);queue.offer(s1);queue.offer(s2);System.out.println(queue.size());for(Student s:queue){System.out.println(s);}queue.clear();System.out.println(queue.size());}
}

?

2.3優(yōu)先級隊列的特性

因為優(yōu)先級隊列是基于堆實現(xiàn)的，所以優(yōu)先級隊列的操作的時間復雜度其實就是堆在操作過程中的時間復雜度

1.插入：

將一個新元素插入到隊列中，并根據(jù)優(yōu)先級調整隊列的順序，時間復雜度為O(logn)

2.刪除：

刪除優(yōu)先級最高的元素，時間復雜度為O(logn)

3.獲取優(yōu)先級最高的元素：

返回優(yōu)先級最高的元素，但不刪除它，時間復雜度為O(1)

4.更新優(yōu)先級：

更新隊列中某個元素的優(yōu)先級，并調整隊列的順序，時間復雜度為O(logn)

5.Priority中放置的元素必須是能夠比較大小的，不能插入無法比較大小的對象，否則會拋出ClassCastException異常

6.不能插入null，否則會拋出NullPointerException

7.PriorityQueue默認情況下是小堆

8.PriorityQueue其內部可以自動擴容

2.4PriorityQueue底層的擴容原理

PriorityQueue的?默認無參構造方法創(chuàng)建的數(shù)組長度為11

如果容量小于64時，是按照oldCapacity的2倍方式擴容的

如果容量大于64時，是按照oldCapacity的1.5倍方式擴容的

如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE來進行擴容

2.5實現(xiàn)一個優(yōu)先級隊列

package datastructure;import java.util.Arrays;public class PriorityQueue {private int elem[];//隊列中有效元素的個數(shù)private int usedSize;private final static int DEFAULT_INIT_SIZE=11;public PriorityQueue(){elem=new int[DEFAULT_INIT_SIZE];}public PriorityQueue(int[] elem){this.elem=elem;this.usedSize=elem.length;int root=((elem.length-2)>>1);for(;root>=0;root--){shiftDown(root,elem.length);}}private void shiftDown(int parent,int len){int child=parent*2+1;while (child<len){if(child+1<len&&elem[child+1]<elem[child]){child++;}if(elem[parent]>elem[child]){swap(elem,parent,child);}else {break;}}}public boolean offer(int value){if(usedSize==elem.length){Arrays.copyOf(elem,2*elem.length);}elem[usedSize]=value;usedSize++;shiftUp(usedSize-1);return true;}private void swap(int[] elem,int a,int b){int tmp=elem[a];elem[a]=elem[b];elem[b]=tmp;}private void shiftUp(int child){int parent=(child-1)/2;while (child>0){if(elem[child]<elem[parent]){swap(elem,parent,child);child=parent;parent=(child-1)/2;}else {break;}}}public int size(){return usedSize;}public int peek(){if(usedSize==0){System.out.println("優(yōu)先級隊列中沒有元素，無法獲取元素");return -1;}return elem[0];}public boolean isEmpty(){return usedSize==0;}public int poll(){if(usedSize==0){System.out.println("優(yōu)先級隊列中沒有元素，無法刪除元素");return -1;}int value=elem[0];swap(elem,0,usedSize-1);usedSize--;shiftDown(0,usedSize-1);return value;}
}

對編寫的代碼進行運行測試：

public class Test {public static void main(String[] args) {PriorityQueue queue=new PriorityQueue();queue.offer(2);queue.offer(4);queue.offer(3);queue.offer(8);queue.offer(7);queue.offer(5);queue.offer(1);System.out.println(queue.peek());int a= queue.poll();System.out.println(a);System.out.println(queue.peek());System.out.println(queue.size());}
}

?