Java 數據結構之堆的概念與應用
java數據結構的堆
什麼是堆
堆指的是使用數組保存完全二叉樹結構，以層次遍歷的方式放入數組中。
如圖：
註意：堆方式適合於完全二叉樹，對於非完全二叉樹若使用堆則會造成空間的浪費
對於根節點與其左右孩子在數組中的下標關系可表示為:left=2parent+1,right=2parent+2,parent=(child-1)/2
堆的類型
對於堆來說一共有兩種類型：一為大根堆，還有一個為小根堆
小根堆
小根堆指的是：所有的根結點的值小於左右孩子結點的值
如圖：
大根堆
大根堆指的是：所有根結點的值大於左右孩子結點的值。
如圖：
當使用堆進行從小到大進行排序時應該使用大堆進行排序
堆的基本操作：創建堆
以創建大堆為例：我們先給定一個數組，該數組在邏輯上可以視為一顆完全二叉樹，但目前並不是堆，但我們可以通過一定的算法將其變化為堆，通常我們從倒數第一個結點進行調整，一直調整到根結點的數，這樣就調整為堆瞭；
如示例：
//建堆前
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));
}
堆的時間復雜度和空間復雜度
建堆時沒有使用額外的空間因此其空間復雜度為O(1);
註意：該函數shiftDown（int[] array,int parent)時間復雜度為O(logn),建堆的時間復雜度為O(n*logn),但是建堆的時間復雜度為O(n)其推導如下：
堆的應用-優先級隊列
概念
我們通常需要按照優先級情況對待處理對象進行處理，比如首先處理優先級最高的對象，然後處理次高的對象.一個簡單的例子：一天晚上，你正在看電視，這時你的父母叫你去廚房幫忙，那麼這時你應該處理最重要的事情：去廚房幫媽媽的忙在這種情況下，我們的數據結構應該提供兩個最基本的操作，一個是返回最高優先級對象，一個是添加新的對象。這種數據結構就是優先級隊列(Priority Queue)。
註意：實現優先級隊列的方式有很多種，一般來說我們一般使用堆來構建優先級隊列
優先級隊列基本操作
入優先級隊列
以大堆為例：
- 首先按尾插方式放入數組
- 比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質，插入結束
- 否則，交換其和雙親位置的值，重新進行 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的優先級隊列
在java中，我們不必單獨創建一個堆用於實現優先級對列
可以使用PriorityQueue
例如：
PriorityQueue<Integer> queue=new PriorityQueue<>();
java中的優先級對列其實是小堆若想使用大堆方法則需要從寫比較方法
方法如下（方法不唯一）
PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator(Integer)){
public int compare(Integer o1,Integer o2){return o2-o1}
};
優先級的使用方法：
| 錯誤處理 | 拋出異常 | 返回特殊值 |
|---|---|---|
| 入隊列 | add(e) | offer(e) |
| 出隊列 | remove() | poll() |
| 隊首元素 | element() | peek() |
堆的常見面試題
最後一塊石頭的重量
最後一塊石頭的重量題
解題思路：該題可以使用變化過的優先級隊列進行解答，即將默認小堆的優先級隊列改為大堆模式的優先級隊列，則將每塊石塊的重量使用循環放入優先級隊列中其自動會把最重的石塊放入隊首，而後，將隊列的頭兩個元素依次取出記為max1,max2,並將sum=max1-max2;如果sum大於0則又放入隊列中不是則繼續重復上訴操作
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個最接近的元素
找到K個最接近的元素
題解主要思路：使用優先級隊列，先判別k是否大於數組長度，大於則直接將數組存放到List，相反則先依次存放k個數，之後將想要存放到優先級隊列中的數-x的絕對值記為sum1,隊列中第一個元素-x的絕對值記為sum2，如果sum1小於sum2則將隊列中第一個元素刪除，將其他數放入隊列中，最後將隊列中元素存放到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對數字
查找和最小的K對數字
主體解題思路：使用優先級隊列將其先改變為大堆模式，使用循環先存放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){
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;
}
}
到此這篇關於Java 數據結構之堆的概念與應用的文章就介紹到這瞭,更多相關Java 數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- Java數據結構之堆(優先隊列)詳解
- Java數據結構專題解析之棧和隊列的實現
- Java數據結構之最小堆和最大堆的原理及實現詳解
- Java中PriorityQueue實現最小堆和最大堆的用法
- Java利用完全二叉樹創建大根堆和小根堆