Java 優先級隊列（堆）

- 1. 優先級隊列（堆）的概念
- 2. 建立大根堆（向下調整算法）
- 3. 堆插入元素（向上調整算法）
- 4. 堆删除元素（向下調整算法）
- 5. 優先級隊列PriorityQueue的特性
- 6. 優先級隊列PriorityQueue的構造方法（預設小根堆）
- 7. Java對象的比較
- - 1. euqals方法
  - 2. Comparable<>接口CompareTo方法（原類上實作）
  - 3. Compartor接口Compare方法（重寫一個類實作）
  - 4. 三種方法的對比
- 8. 大根堆的建立
- 9. Top-k問題
- - 1.整體建小根堆
  - 2.局部建容量為k的大根堆

1. 優先級隊列（堆）的概念

優先級隊列PriorityQueue底層使用了堆這種資料結構，堆是一棵順序存儲的完全二叉樹。
堆的性質

①堆中某個結點的值不大于/不小于其父節點的值（因為一旦稱之為堆，則一定是大根堆or小根堆）

②堆是一棵完全二叉樹（因為堆是順序存儲的二叉樹，如果非完全二叉樹就會存在null結點浪費了數組順序存儲的空間）
堆是一顆完全二叉樹，采用按層編号進行順序存儲，十分的高效。那麼假設i為結點在數組中的下标，則有：

①i的父結點下标為(i-1)/2

②i的左孩子下标為2i+1，i的右孩子下标為2i+2

2. 建立大根堆（向下調整算法）

思路：從最後一個非葉子結點開始進行向下調整，如果父節點的值已經滿足大于兩個孩子結點的值，則直接跳出循環調整下一個結點；否則就與孩子結點進行交換，交換完之後可能會造成子樹不滿足堆的性質，是以需要繼續向下調整。

建堆的時間複雜度為O(N)

向下調整的時間複雜度為O(logN)

代碼：

//建立大根堆（向下調整）
    public void createHeap() {
        //從最後一個非葉子結點開始進行向下調整
        for (int i = (usedsize-1-1) / 2; i >= 0; i--) {
            shiftDown(i,usedsize);
        }
    }
    public void shiftDown(int parent,int len) {
        int child = 2 * parent + 1;

        while (child < len) {
            if (child + 1 < len && elem[child] < elem[child +1]) {
                child = child + 1;
            }

            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

3. 堆插入元素（向上調整算法）

思路：堆插入元素是直接插在有效元素的後面的【注定是最後一個葉子結點】，然後對這個葉子結點所在的位置進行向上調整，注意這個葉子不用在跟其兄弟葉子進行比較，隻用跟其父結點進行比較。

向上調整的時間複雜度為O(logN)

向上調整建堆的時間複雜度為O(NlogN)

是以一般選用上下調整的算法建堆，因為最後2層的結點最多，要調整的元素也多，時間會變慢。

代碼：

public void inset(int val) {
        if (isFull()) {
            addSize();
        }
        elem[usedsize++] = val;
        //向上調整算法
        shiftUp(usedsize-1);
    }
    public void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (elem[parent] < elem[child]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    public boolean isFull() {
        if (elem.length == usedsize) {
            return true;
        }
        return false;
    }
    public void addSize() {
        elem = Arrays.copyOf(elem,elem.length*2);
    }

4. 堆删除元素（向下調整算法）

思路：每次删除的元素是堆頂的元素，将堆頂元素和堆中的最後一個元素進行交換，然後向下調整交換後的堆頂元素。

代碼：

public void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    public void deleElem() {
        if (usedsize <= 0) {
            return;
        }
        swap(0,usedsize-1);
        usedsize--;
        shiftDown(0,usedsize);
    }

5. 優先級隊列PriorityQueue的特性

PriorityQueue中放置的元素必須要可比較，否則就不能進行向上/下調整了，并且會抛出類型轉換異常ClassCastException。
不能插入null對象，否則會抛出空指針異常NullPointerException。
插入和删除元素的時間複雜度是O(logN)，即樹的高度。
PriorityQueue的底層使用堆資料結構，預設是小根堆，即每次擷取到的元素都是最小的。

6. 優先級隊列PriorityQueue的構造方法（預設小根堆）

無參構造方法執行個體化優先級隊列對象

底層代碼：

Java 優先級隊列（堆）

分析：會建立一個空的優先級隊列，預設容量是11

傳入一個整型參數執行個體化優先級隊列對象

底層代碼：

Java 優先級隊列（堆）

分析：會建立一個初始容量為initialCapacity的優先級隊列，這裡建立的容量是100，注意初始容量不能小于1，否則會抛出異常。

傳入一個集合參數執行個體化優先級隊列對象

LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(list);

分析：用LinkedList對象來構造一個優先級隊列的對象。

注意：執行個體化優先級對象預設建立的是小根堆，如果是大根堆需要提供比較器【涉及到對象的比較】。

7. Java對象的比較

在Java中，基本資料類型可以大于、小于、等于去比較，但是對于對象的比較則需要用到以下幾種方法。

1. euqals方法

①如果自定義的類沒有重寫euqals方法，那麼預設是繼承的Object類中的equals方法，使用的是“==”。

Java 優先級隊列（堆）

②自定義類重寫equals方法

Java 優先級隊列（堆）

注意：euqals隻能按照相等進行比較，不能比較大于、小于。

測試：

Student student1 = new Student("張三",22);
        Student student2 = new Student("張三",22);
        System.out.println(student1.equals(student2));

如果沒有在Student類中重寫euqals方法，則輸出false；如果重寫了euqals方法，則輸出true。

2. Comparable<>接口CompareTo方法（原類上實作）

Java 優先級隊列（堆）

注意：

①在接口的後面要加上泛型

②這種寫法侵入性比較強，不易修改

3. Compartor接口Compare方法（重寫一個類實作）

class AgeComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age;
    }
}

執行個體化構造器對象，并且調用構造器中的compare方法。

public static void main(String[] args) {
        Student student1 = new Student("張三",22);
        Student student2 = new Student("三",22);
        AgeComparator ageComparator = new AgeComparator();
        System.out.println(ageComparator.compare(student1, student2));
    }

4. 三種方法的對比

比較的方法	說明
Object.equals	不重寫的話是繼承Object的方法，需要重寫覆寫，隻能比較相等與否
Comparable.compareTo	需要手動實作接口，不夠靈活
Comparator.compare	需要實作一個比較器類對象

8. 大根堆的建立

優先級隊列預設是小根堆，如果要建立大根堆，那麼就傳入比較方法。

比較器：（注意用到泛型）

class IntCompare implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

執行個體化比較器、優先級隊列對象，并傳入比較器參數

public class MaxHeap {
    public static void main(String[] args) {
        IntCompare intCompare = new IntCompare();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(intCompare);
        priorityQueue.offer(3);
        priorityQueue.offer(2);
        priorityQueue.offer(9);
        priorityQueue.offer(1);
        System.out.println(priorityQueue);
    }
}

運作結果：

Java 優先級隊列（堆）

9. Top-k問題

力扣 17.14. 最小K個數

設計一個算法，找出數組中最小的k個數。以任意順序傳回這k個數均可。

示例：

輸入： arr = [1,3,5,7,2,4,6,8], k = 4

輸出： [1,2,3,4]

1.整體建小根堆

思路：因為有大量的資料需要排序，是以采用堆這種資料結構，把所有的資料全部建成一個小根堆，然後每次取堆頂的元素。

代碼：

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //小根堆
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}

2.局部建容量為k的大根堆

思路：建立容量為k的大根堆，如果下一個待比較的元素比大根堆的元素小，就把大根堆的元素出堆，下一個待比較的元素進入堆中，這樣最後得到的就是k個最小的元素。

【注意要判斷數組為空以及 k為0的情況，否則會出現空指針異常】

代碼：

class IntComp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr.length == 0 || k == 0) {
            return ret;
        }
        //建立大根堆
        IntComp intComp = new IntComp();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(intComp);
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
    
}

Java 優先級隊列（堆）

目錄

1. 優先級隊列（堆）的概念

2. 建立大根堆（向下調整算法）

3. 堆插入元素（向上調整算法）

4. 堆删除元素（向下調整算法）

5. 優先級隊列PriorityQueue的特性

6. 優先級隊列PriorityQueue的構造方法（預設小根堆）

7. Java對象的比較

1. euqals方法

2. Comparable<>接口CompareTo方法（原類上實作）

3. Compartor接口Compare方法（重寫一個類實作）

4. 三種方法的對比

8. 大根堆的建立

9. Top-k問題

1.整體建小根堆

2.局部建容量為k的大根堆

繼續閱讀

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

hdu7108哈希