java數(shù)據(jù)結(jié)構(gòu)的堆
什么是堆
堆指的是使用數(shù)組保存完全二叉樹結(jié)構(gòu)，以層次遍歷的方式放入數(shù)組中。
如圖：
注意：堆方式適合于完全二叉樹，對于非完全二叉樹若使用堆則會造成空間的浪費
對于根節(jié)點與其左右孩子在數(shù)組中的下標(biāo)關(guān)系可表示為:left=2parent+1,right=2parent+2,parent=(child-1)/2
堆的類型
對于堆來說一共有兩種類型：一為大根堆，還有一個為小根堆
小根堆
小根堆指的是：所有的根結(jié)點的值小于左右孩子結(jié)點的值
如圖：
大根堆
大根堆指的是：所有根結(jié)點的值大于左右孩子結(jié)點的值。
如圖：
當(dāng)使用堆進行從小到大進行排序時應(yīng)該使用大堆進行排序
堆的基本操作：創(chuàng)建堆
以創(chuàng)建大堆為例：我們先給定一個數(shù)組，該數(shù)組在邏輯上可以視為一顆完全二叉樹，但目前并不是堆，但我們可以通過一定的算法將其變化為堆，通常我們從倒數(shù)第一個結(jié)點進行調(diào)整，一直調(diào)整到根結(jié)點的數(shù)，這樣就調(diào)整為堆了；
如示例：
//建堆前
int array[]={1,5,3,8,7,6};
//建堆后
int array[]={ 8,7,6,5,1,3 };
調(diào)整方式：
第一步：先將數(shù)組還原成一個完全二叉樹
如圖：
第二步：如果倒數(shù)第一個葉子結(jié)點有兄弟結(jié)點則先與兄弟結(jié)點比較大小然后再取大的結(jié)點與父結(jié)點比較大小，如果沒有兄弟結(jié)點則直接與父結(jié)點比較大小，如果值比父結(jié)點值大則交換值，一直這樣調(diào)整到根節(jié)點的樹，就可以調(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));
}
堆的時間復(fù)雜度和空間復(fù)雜度
建堆時沒有使用額外的空間因此其空間復(fù)雜度為O(1);
注意：該函數(shù)shiftDown（int[] array,int parent)時間復(fù)雜度為O(logn),建堆的時間復(fù)雜度為O(n*logn),但是建堆的時間復(fù)雜度為O(n)其推導(dǎo)如下：
堆的應(yīng)用-優(yōu)先級隊列
概念
我們通常需要按照優(yōu)先級情況對待處理對象進行處理，比如首先處理優(yōu)先級最高的對象，然后處理次高的對象.一個簡單的例子：一天晚上，你正在看電視，這時你的父母叫你去廚房幫忙，那么這時你應(yīng)該處理最重要的事情：去廚房幫媽媽的忙在這種情況下，我們的數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個最基本的操作，一個是返回最高優(yōu)先級對象，一個是添加新的對象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列(Priority Queue)。
注意：實現(xiàn)優(yōu)先級隊列的方式有很多種，一般來說我們一般使用堆來構(gòu)建優(yōu)先級隊列
優(yōu)先級隊列基本操作
入優(yōu)先級隊列
以大堆為例：
- 首先按尾插方式放入數(shù)組
- 比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質(zhì)，插入結(jié)束
- 否則，交換其和雙親位置的值，重新進行 2、3 步驟
- 直到根結(jié)點
如圖：
核心代碼如下：
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) {
//先判斷隊列是否已經(jīng)滿，如果以滿則擴容
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)先級隊列首元素
注意：為了防止破壞堆的結(jié)構(gòu)，刪除時并不是直接將堆頂元素刪除，而是用數(shù)組的最后一個元素替換堆頂元素，然后通過向
下調(diào)整方式重新調(diào)整成堆
核心代碼如下：
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("優(yōu)先級隊列為空");
}
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;
//進入這個循環(huán) 說明最起碼你有左孩子
while (child < this.usedSize) {
//該條件進入是判斷其是否有右兄弟
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é)點比父親節(jié)點小 直接結(jié)束了
}
}
}
}
java的優(yōu)先級隊列
在java中，我們不必單獨創(chuàng)建一個堆用于實現(xiàn)優(yōu)先級對列
可以使用PriorityQueue
例如：
PriorityQueue<Integer> queue=new PriorityQueue<>();
java中的優(yōu)先級對列其實是小堆若想使用大堆方法則需要從寫比較方法
方法如下（方法不唯一）
PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator(Integer)){
public int compare(Integer o1,Integer o2){return o2-o1}
};
優(yōu)先級的使用方法：
| 錯誤處理 | 拋出異常 | 返回特殊值 |
|---|---|---|
| 入隊列 | add(e) | offer(e) |
| 出隊列 | remove() | poll() |
| 隊首元素 | element() | peek() |
堆的常見面試題
最后一塊石頭的重量
最后一塊石頭的重量題
解題思路：該題可以使用變化過的優(yōu)先級隊列進行解答，即將默認小堆的優(yōu)先級隊列改為大堆模式的優(yōu)先級隊列，則將每塊石塊的重量使用循環(huán)放入優(yōu)先級隊列中其自動會把最重的石塊放入隊首，而后，將隊列的頭兩個元素依次取出記為max1,max2,并將sum=max1-max2;如果sum大于0則又放入隊列中不是則繼續(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個最接近的元素
找到K個最接近的元素
題解主要思路：使用優(yōu)先級隊列，先判別k是否大于數(shù)組長度，大于則直接將數(shù)組存放到List，相反則先依次存放k個數(shù)，之后將想要存放到優(yōu)先級隊列中的數(shù)-x的絕對值記為sum1,隊列中第一個元素-x的絕對值記為sum2，如果sum1小于sum2則將隊列中第一個元素刪除，將其他數(shù)放入隊列中，最后將隊列中元素存放到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對數(shù)字
查找和最小的K對數(shù)字
主體解題思路：使用優(yōu)先級隊列將其先改變?yōu)榇蠖涯Ｊ剑褂醚h(huán)先存放k個元素，之后想要存入隊列的元素與隊頭元素比較，如果比隊頭元素小則刪除隊頭元素，存放該元素，相反則繼續(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)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/weixin_49830664/article/details/120807877
