java資料結構的堆
文章目錄
- java資料結構的堆
- 什么是堆
- 堆的型別
- 小根堆
- 大根堆
- 堆的基本操作：創建堆
- 堆的時間復雜度和空間復雜度
- 堆的應用-優先級佇列
- 概念
- 優先級佇列基本操作
- 入優先級佇列
- 出優先級佇列首元素
- java的優先級佇列
- 堆的常見面試題
- 最后一塊石頭的重量
- 找到K個最接近的元素
- 查找和最小的K對數字
什么是堆
堆指的是使用陣列保存完全二叉樹結構，以層次遍歷的方式放入陣列中，
如圖：
注意：堆方式適合于完全二叉樹，對于非完全二叉樹若使用堆則會造成空間的浪費
對于根節點與其左右孩子在陣列中的下標關系可表示為: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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/321222.html
標籤：java
上一篇：還記不住Spring Bean的生命周期？看這篇你就知道方法了！
下一篇：Data Type And Operator - 資料型別和運算子 （JavaSE- 最詳細的介紹，因為這算是我最長的一篇了）