Java數(shù)據(jù)結(jié)構(gòu)之堆(優(yōu)先隊列)詳解
堆的性質(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é)點大于左右兩個子節(jié)點的完全二叉樹 （父親節(jié)點大于其子節(jié)點），叫做大堆，或者大根堆，或者最大堆 。
小堆：根節(jié)點小于左右兩個子節(jié)點的完全二叉樹叫 小堆（父親節(jié)點小于其子節(jié)點），或者小根堆，或者最小堆。
堆的向下調(diào)整
現(xiàn)在有一個數(shù)組，邏輯上是完全二叉樹，我們通過從根節(jié)點開始的向下調(diào)整算法可以把它調(diào)整成一個小堆或者大堆。向下調(diào)整算法有一個前提：左右子樹必須是一個堆，才能調(diào)整。
以小堆為例：
1、先讓左右孩子結(jié)點比較，取最小值。
2、用較小的那個孩子結(jié)點與父親節(jié)點比較，如果孩子結(jié)點<父親節(jié)點，交換，反之，不交換。
3、循環(huán)往復(fù)，如果孩子結(jié)點的下標(biāo)越界，則說明已經(jīng)到了最后，就結(jié)束。
代碼示例：
//parent: 每棵樹的根節(jié)點
//len: 每棵樹的調(diào)整的結(jié)束位置
public void shiftDown(int parent,int len){
int child=parent*2+1; //因為堆是完全二叉樹，沒有左孩子就一定沒有右孩子，所以最起碼是有左孩子的，至少有1個孩子
while(child<len){
if(child+1<len && elem[child]<elem[child+1]){
child++;//兩孩子結(jié)點比較取較小值
}
if(elem[child]<elem[parent]){
int tmp=elem[parent];
elem[parent]=elem[child];
elem[child]=tmp;
parent=child;
child=parent*2+1;
}else{
break;
}
}
}堆的建立
給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆（左右子樹不滿足都是大堆或者小堆），現(xiàn)在我們通過算法，把它構(gòu)建成一個堆（大堆或者小堆）。該怎么做呢？這里我們從倒數(shù)的第一個非葉子節(jié)點的子樹開始調(diào)整，一直調(diào)整到根節(jié)點的樹，就可以調(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），因為堆為一棵完全二叉樹，滿二叉樹也是一種完全二叉樹，我們用滿二叉樹（最壞情況下）來證明。
堆得向上調(diào)整
現(xiàn)在有一個堆，我們需要在堆的末尾插入數(shù)據(jù)，再對其進行調(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;
}
}
}堆的常用操作
入隊列
往堆里面加入元素，就是往最后一個位置加入，然后在進行向上調(diào)整。
public boolean isFull(){
return elem.length==useSize;
}
public void offer(int val){
if(isFull()){
elem= Arrays.copyOf(elem,2*elem.length);//擴容
}
elem[useSize++]=val;
shiftup(useSize-1);
}出隊列
把堆里元素刪除，就把堆頂元素和最后一個元素交換，然后向整個數(shù)組大小減一，最后向下調(diào)整，就刪除了棧頂元素。
public boolean isEmpty(){
return useSize==0;
}
public int poll(){
if(isEmpty()){
throw new RuntimeException("優(yōu)先級隊列為空");
}
int tmp=elem[0];
elem[0]=elem[useSize-1];
elem[useSize-1]=tmp;
useSize--;
shiftDown(0,useSize);
return tmp;
}獲取隊首元素
public int peek() {
if (isEmpty()) {
throw new RuntimeException("優(yōu)先級隊列為空");
}
return elem[0];
}TopK 問題
給你6個數(shù)據(jù)，求前3個最大數(shù)據(jù)。這時候我們用堆怎么做的？
解題思路：
1、如果求前K個最大的元素，要建一個小根堆。
2、如果求前K個最小的元素,要建一個大根堆。
3、第K大的元素。建一個小堆,堆頂元素就是第K大的元素。
4、第K小的元素。建一個大堆,堆頂元素就是第K大的元素。
例子
舉個例子：求前n個最大數(shù)據(jù)
代碼示例：
public static int[] topK(int[] array,int k){
//創(chuàng)建一個大小為K的小根堆
PriorityQueue<Integer> minHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
});
//遍歷數(shù)組中元素，將前k個元素放入隊列中
for(int i=0;i<array.length;i++){
if(minHeap.size()<k){
minHeap.offer(array[i]);
}else{
//從k+1個元素開始，分別和堆頂元素比較
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ù)組排序
再者說如果要對一個數(shù)組進行從小到大排序，要借助大根堆還是小根堆呢？
---->大根堆
代碼示例：
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--;
}
}到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之堆(優(yōu)先隊列)詳解的文章就介紹到這了,更多相關(guān)Java堆內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
基于Retrofit+Rxjava實現(xiàn)帶進度顯示的下載文件
在Java的JDBC使用中設(shè)置事務(wù)回滾的保存點的方法
Java postgresql數(shù)組字段類型處理方法詳解
Mybatis-Plus的多數(shù)據(jù)源你了解嗎
Java圖形化界面設(shè)計之布局管理器之BorderLayout案例詳解