一：堆

1.1 堆的基本概念

堆分為兩種：大堆和小堆。它們之間的區(qū)別在于元素在堆中的排列順序和訪問方式。

1. 大堆（Max Heap）：

在大堆中，父節(jié)點(diǎn)的值比它的子節(jié)點(diǎn)的值要大。也就是說，堆的根節(jié)點(diǎn)是堆中最大的元素。大堆被用于實現(xiàn)優(yōu)先級隊列，其中根節(jié)點(diǎn)的元素始終是隊列中最大的元素。

大堆的特點(diǎn)：

• 對于每個父節(jié)點(diǎn)，它的值大于或等于其子節(jié)點(diǎn)的值。

3. 小堆（Min Heap）：

在小堆中，父節(jié)點(diǎn)的值比它的子節(jié)點(diǎn)的值要小。也就是說，堆的根節(jié)點(diǎn)是堆中最小的元素。小堆常用于實現(xiàn)優(yōu)先級隊列，其中根節(jié)點(diǎn)的元素始終是隊列中最小的元素。

小堆的特點(diǎn)：

• 對于每個父節(jié)點(diǎn)，它的值小于或等于其子節(jié)點(diǎn)的值。

以下是一個示例圖示，展示了一個包含7個元素的大堆和小堆的結(jié)構(gòu)：

大堆：
        90
      /    \
    75      30
   /  \    /  \
  20   15  10   7

小堆：
        7
      /   \
    10     30
   /  \   /  \
  20   15 75  90

在大堆中，父節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值，而在小堆中，父節(jié)點(diǎn)的值小于子節(jié)點(diǎn)的值。

注意：堆總是一顆完全二叉樹

1.2堆的存儲方式

從堆的概念可知，堆是一棵完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲，

注意：對于非完全二叉樹，則不適合使用順序方式進(jìn)行存儲，因為為了能夠還原二叉樹，空間中必須要存儲空節(jié)點(diǎn)，就會導(dǎo)致空間利用率比較低。

將元素存儲到數(shù)組中后，可以根據(jù)二叉樹章節(jié)的性質(zhì)5對樹進(jìn)行還原。

假設(shè)i為節(jié)點(diǎn)在數(shù)組中的下標(biāo)，則有：

• 如果i為0，則i表示的節(jié)點(diǎn)為根節(jié)點(diǎn)
• 節(jié)點(diǎn)i的左孩子下標(biāo)為2 * i + 1 ( 2 * i + 1 小于節(jié)點(diǎn)個數(shù)，否則沒有左孩子 )
• 節(jié)點(diǎn)i的右孩子下標(biāo)為2 * i + 2 ( 2 * i + 2 小于節(jié)點(diǎn)個數(shù)，否則沒有右孩子 )

1.3 堆的下沉

對于集合{ 27,15,19,18,28,34,65,49,25,37 }中的數(shù)據(jù)，如果將其創(chuàng)建成小堆呢？

仔細(xì)觀察上圖后發(fā)現(xiàn)：根節(jié)點(diǎn)的左右子樹已經(jīng)完全滿足堆的性質(zhì)，因此只需將根節(jié)點(diǎn)向下調(diào)整好即可。

下面是代碼實現(xiàn)：

// shiftDown方法用來實現(xiàn)下沉操作
// array參數(shù)是待構(gòu)建小堆的數(shù)組
// parent參數(shù)是當(dāng)前需要下沉的節(jié)點(diǎn)的索引
public void shiftDown(int[] array, int parent) {
    int length = array.length;
    int child = 2 * parent + 1; // 左子節(jié)點(diǎn)索引
    
    while (child < length) {
        // 找到左右孩子中較小的孩子
        if (child + 1 < length && array[child] > array[child + 1]) {
            child++; // 如果右子節(jié)點(diǎn)存在并且小于左子節(jié)點(diǎn)的值，則將child指向右子節(jié)點(diǎn)
        }
        
        // 如果當(dāng)前節(jié)點(diǎn)小于或等于左右子節(jié)點(diǎn)中較小的節(jié)點(diǎn)，說明已經(jīng)符合小堆要求
        if (array[parent] <= array[child]) {
            break;
        }
        
        // 否則，交換當(dāng)前節(jié)點(diǎn)和較小子節(jié)點(diǎn)的值，接著需要繼續(xù)向下調(diào)整
        int temp = array[parent];
        array[parent] = array[child];
        array[child] = temp;
        
        parent = child;
        child = 2 * parent + 1;
    }
}

這段代碼實現(xiàn)了堆排序中的下沉操作（也稱為向下調(diào)整或堆化）。下沉操作用于維護(hù)小堆的性質(zhì)，確保父節(jié)點(diǎn)永遠(yuǎn)小于或等于其子節(jié)點(diǎn)。

時間復(fù)雜度分析：最壞的情況即圖示的情況，從根一路比較到葉子，比較的次數(shù)為完全二叉樹的高度，即時間復(fù)雜度為O（log n）

1.4 堆的創(chuàng)建

那對于普通的序列{ 1,5,3,8,7,6 }，即根節(jié)點(diǎn)的左右子樹不滿足堆的特性，又該如何調(diào)整呢？

參考代碼：

public static void createHeap(int[] array) {
  // 找倒數(shù)第一個非葉子節(jié)點(diǎn)，從該節(jié)點(diǎn)位置開始往前一直到根節(jié)點(diǎn)，遇到一個節(jié)點(diǎn)，應(yīng)用向下調(diào)整
  int root = ((array.length-2)>>1);
  for (; root >= 0; root--) {
    shiftDown(array, root);
 }
}

1.5建堆的時間復(fù)雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復(fù)雜度本來看的就是近似值，多幾個節(jié)點(diǎn)不影響最終結(jié)果)：

因此：建堆的時間復(fù)雜度為O(N)。

1.6堆的插入和刪除

1.6.1 堆的插入

堆的插入總共需要兩個步驟：

1. 先將元素放入到底層空間中(注意：空間不夠時需要擴(kuò)容)
2. 將最后新插入的節(jié)點(diǎn)向上調(diào)整，直到滿足堆的性質(zhì)

下面是堆的刪除操作的代碼實現(xiàn)，包含詳細(xì)注釋：

public void shiftUp(int child) {
  // 找到child的雙親
  int parent = (child - 1) / 2;
 
  while (child > 0) {
    // 如果雙親比孩子大，parent滿足堆的性質(zhì)，調(diào)整結(jié)束
    if (array[parent] > array[child]) {
      break;
   }
    else{
      // 將雙親與孩子節(jié)點(diǎn)進(jìn)行交換
      int t = array[parent];
      array[parent] = array[child];
      array[child] = t;
   
      // 小的元素向下移動，可能到值子樹不滿足對的性質(zhì)，因此需要繼續(xù)向上調(diào)增
      child = parent;
      parent = (child - 1) / 1;
   }
 }
}

1.6.2 堆的刪除

注意：堆的刪除一定刪除的是堆頂元素。具體如下：

1. 將堆頂元素對堆中最后一個元素交換
2. 將堆中有效數(shù)據(jù)個數(shù)減少一個
3. 對堆頂元素進(jìn)行向下調(diào)整

下面是堆的刪除操作的代碼實現(xiàn)，包含詳細(xì)注釋：

public void deleteTop() {
  // 將堆頂元素與堆中最后一個元素交換
  array[0] = array[size - 1];
 
  // 堆中有效數(shù)據(jù)個數(shù)減少一個
  size--;
 
  // 對堆頂元素進(jìn)行向下調(diào)整
  int parent = 0; // 當(dāng)前節(jié)點(diǎn)的索引
 
  // 持續(xù)向下調(diào)整，直到滿足堆的性質(zhì)
  while (true) {
    // 左孩子節(jié)點(diǎn)的索引
    int leftChild = parent * 2 + 1;
    // 右孩子節(jié)點(diǎn)的索引
    int rightChild = leftChild + 1;
 
    // 父節(jié)點(diǎn)與左右孩子節(jié)點(diǎn)中值最大的節(jié)點(diǎn)進(jìn)行交換
    int maxChild = parent; // 最大值節(jié)點(diǎn)的索引
 
    // 如果左孩子存在且大于父節(jié)點(diǎn)，則更新最大值節(jié)點(diǎn)
    if (leftChild < size && array[leftChild] > array[maxChild]) {
      maxChild = leftChild;
    }
 
    // 如果右孩子存在且大于當(dāng)前最大值節(jié)點(diǎn)，則更新最大值節(jié)點(diǎn)
    if (rightChild < size && array[rightChild] > array[maxChild]) {
      maxChild = rightChild;
    }
 
    // 如果最大值節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)本身，則調(diào)整結(jié)束 
    if (maxChild == parent) {
      break;
    } else {
      // 交換最大節(jié)點(diǎn)與父節(jié)點(diǎn)
      int temp = array[parent];
      array[parent] = array[maxChild];
      array[maxChild] = temp;
 
      // 更新當(dāng)前節(jié)點(diǎn)為最大值節(jié)點(diǎn)
      parent = maxChild;
    }
  }
}

二：優(yōu)先級隊列

2.1 概念

前面介紹過隊列，隊列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu).

但有些情況下，操作的數(shù)據(jù)可能帶有優(yōu)先級，出隊列時，可能需要優(yōu)先級高的元素先出隊列，該中場景下，使用隊列顯然不合適，比如：在手機(jī)上玩游戲的時候，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話；初中那會班主任排座位時可能會讓成績好的同學(xué)先挑座位。

在這種情況下，數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個最基本的操作，一個是返回最高優(yōu)先級對象，一個是添加新的對象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列(Priority Queue)。

2.2堆的使用

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種類型的優(yōu)先級隊列，PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的，本文主要介紹PriorityQueue。

關(guān)于PriorityQueue的使用要注意：

1. 使用時必須導(dǎo)入PriorityQueue所在的包

2. PriorityQueue中放置的元素必須要能夠比較大小，不能插入無法比較大小的對象，否則會拋出ClassCastException異常

3. 不能插入null對象，否則會拋出NullPointerException

4. 沒有容量限制，可以插入任意多個元素，其內(nèi)部可以自動擴(kuò)容

5. PriorityQueue底層使用了堆數(shù)據(jù)結(jié)構(gòu)

6. PriorityQueue默認(rèn)情況下是小堆—即每次獲取到的元素都是最小的元素

PriorityQueue中常見的構(gòu)造方法：

下面是使用示例：

static void TestPriorityQueue(){
    // 創(chuàng)建一個空的優(yōu)先級隊列，底層默認(rèn)容量是11
    PriorityQueue<Integer> q1 = new PriorityQueue<>();
    
    // 創(chuàng)建一個空的優(yōu)先級隊列，底層的容量為initialCapacity
    PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
    ArrayList<Integer> list = new ArrayList<>();
    list.add(4);
    list.add(3);
    list.add(2);
    list.add(1);
    
    // 用ArrayList對象來構(gòu)造一個優(yōu)先級隊列的對象
    // q3中已經(jīng)包含了三個元素
    PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
    System.out.println(q3.size());//4
    System.out.println(q3.peek());//1
 }

注意：默認(rèn)情況下，PriorityQueue隊列是小堆，如果需要大堆需要用戶提供比較器

// 用戶自己定義的比較器：直接實現(xiàn)Comparator接口，然后重寫該接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
  @Override
  public int compare(Integer o1, Integer o2) {
    return o2-o1;
 }
}
public class TestPriorityQueue {
  public static void main(String[] args) {
    PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
    p.offer(4);
    p.offer(3);
    p.offer(2);
    p.offer(1);
    p.offer(5);
    System.out.println(p.peek());
 }
}

下面是 PriorityQueue中常用的方法：

下面是這些方法的使用示例：

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        // 測試插入元素
        heap.offer(10); // 返回 true
        heap.offer(5); // 返回 true
        heap.offer(15); // 返回 true
        heap.offer(2); // 返回 true
        
        // 測試獲取優(yōu)先級最高的元素
        // 結(jié)果為 2
        System.out.println(heap.peek());
        
        // 測試移除優(yōu)先級最高的元素
        // 結(jié)果為 2
        System.out.println(heap.poll());
        
        // 測試獲取有效元素的個數(shù)
        // 結(jié)果為 3
        System.out.println(heap.size());
        
        // 測試清空優(yōu)先級隊列
        heap.clear();
        
        // 測試檢測優(yōu)先級隊列是否為空
        // 結(jié)果為 true
        System.out.println(heap.isEmpty());
    }
}

以下是JDK 1.8中，PriorityQueue的擴(kuò)容方式：

優(yōu)先級隊列的擴(kuò)容說明：

• 如果容量小于64時，是按照oldCapacity的2倍方式擴(kuò)容的
• 如果容量大于等于64，是按照oldCapacity的1.5倍方式擴(kuò)容的
• 如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE來進(jìn)行擴(kuò)容

MAX_ARRAY_SIZE等于Integer.MAX_VALUE - 8，等于 2,147,483,639。

2.3 用堆模擬實現(xiàn)優(yōu)先級隊列

我們通過堆可以模擬實現(xiàn)優(yōu)先級隊列，因為堆具有以下特性：

1. 大堆或小堆：堆可以是大堆或小堆，其中大堆意味著父節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值，而小堆意味著父節(jié)點(diǎn)的值小于或等于其子節(jié)點(diǎn)的值。
2. 優(yōu)先級定義：我們可以將堆中的元素與優(yōu)先級相關(guān)聯(lián)。較高的優(yōu)先級可以根據(jù)堆類型來確定是最大值還是最小值。

優(yōu)先性在優(yōu)先級隊列中體現(xiàn)在以下方面：

1. 插入元素：由于堆的性質(zhì)，插入的元素會按照其優(yōu)先級找到正確的位置插入。較高優(yōu)先級的元素會被放置在堆的頂部（根節(jié)點(diǎn)）。
2. 刪除元素：從堆中刪除元素時，會刪除具有最高（最大堆）或最低（最小堆）優(yōu)先級的元素。這樣，每次刪除的元素都是具有最高/最低優(yōu)先級的元素。

通過以上方式，可以使用堆來實現(xiàn)優(yōu)先級隊列，確保具有更高優(yōu)先級的元素優(yōu)先被處理或刪除。

下面我們基于堆來模擬實現(xiàn)一個優(yōu)先級隊列：

public class MyPriorityQueue {
  // 演示作用，不再考慮擴(kuò)容部分的代碼
  private int[] array = new int[100];  // 使用數(shù)組來存儲元素
  private int size = 0;  // 當(dāng)前隊列的大小

  // 向優(yōu)先隊列中插入元素
  public void offer(int e) {
    array[size++] = e;  // 將元素插入數(shù)組末尾
    shiftUp(size - 1);  // 對插入的元素進(jìn)行上浮操作，以保持堆的性質(zhì)
  }

  // 彈出并返回優(yōu)先隊列中最高優(yōu)先級的元素
  public int poll() {
    int oldValue = array[0];  // 保存堆頂元素的值
    array[0] = array[--size];  // 將堆尾元素移到堆頂
    shiftDown(0);  // 對堆頂元素進(jìn)行下沉操作，以保持堆的性質(zhì)
    return oldValue;  // 返回彈出的元素值
  }

  // 返回優(yōu)先隊列中最高優(yōu)先級的元素
  public int peek() {
    return array[0];  // 直接返回堆頂元素的值
  }
}

請注意，此處的代碼僅展示了演示目的，沒有考慮擴(kuò)容部分的代碼實現(xiàn)。

三： 堆的應(yīng)用

3.1PriorityQueue的實現(xiàn)

用堆作為底層結(jié)構(gòu)封裝優(yōu)先級隊列，這點(diǎn)我們已經(jīng)講過，在此不過多贅述

3.2堆排序

堆排序即利用堆的思想來進(jìn)行排序，總共分為兩個步驟：

1. 建堆

升序：建大堆
降序：建小堆

2. 利用堆刪除思想來進(jìn)行排序

建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。

3.3Top-k問題

TOP-K問題：即求數(shù)據(jù)集合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。

比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等 , 我們可以通過使用堆來解決TOP-K問題，具體步驟如下：

一： 創(chuàng)建一個大小為K的最小堆（或最大堆，取決于你是求前K個最小值還是最大值）。

二：遍歷數(shù)據(jù)集合，對于每個元素執(zhí)行以下操作：

• 如果堆的大小小于K，將當(dāng)前元素插入堆中。
• 如果堆的大小等于K，比較當(dāng)前元素與堆頂元素的大小
• 如果當(dāng)前元素大于堆頂元素（最小堆），將堆頂元素彈出，將當(dāng)前元素插入堆中。
• 如果當(dāng)前元素小于堆頂元素（最大堆），跳過當(dāng)前元素。

三： 遍歷完數(shù)據(jù)集合后，堆中的元素即為前K個最小（或最大）的元素。

下面是一個使用Java實現(xiàn)堆解決TOP-K問題的示例代碼：

import java.util.PriorityQueue;

public class TopK {
    public static void main(String[] args) {
        int[] nums = {9, 3, 7, 5, 1, 8, 2, 6, 4};
        int k = 4;

        findTopK(nums, k);
    }

    private static void findTopK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        System.out.println("Top " + k + " elements:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
    }
}

以上示例中，對數(shù)組nums求前4個最小元素，使用了PriorityQueue實現(xiàn)了一個小頂堆。遍歷數(shù)組時，根據(jù)堆的大小和當(dāng)前元素與堆頂元素的比較進(jìn)行插入和調(diào)整。最后，打印出堆中的元素即為前4個最小的元素。

四：java對象的比較

4.1PriorityQueue中插入對象

優(yōu)先級隊列在插入元素時有個要求：插入的元素不能是null或者元素之間必須要能夠進(jìn)行比較，為了簡單起見，我們只是插入了Integer類型，那優(yōu)先級隊列中能否插入自定義類型對象呢？

class Card {
  public int rank; // 數(shù)值
  public String suit; // 花色
  
  public Card(int rank, String suit) {
    this.rank = rank;
    this.suit = suit;
 }
}
public class TestPriorityQueue {
  public static void TestPriorityQueue()
 {
    PriorityQueue<Card> p = new PriorityQueue<>();
    p.offer(new Card(1, "?"));
    p.offer(new Card(2, "?"));
 }
  public static void main(String[] args) {
    TestPriorityQueue();
 }
}

優(yōu)先級隊列底層使用堆，而向堆中插入元素時，為了滿足堆的性質(zhì)，必須要進(jìn)行元素的比較，而此時Card是沒有辦法直接進(jìn)行比較的，因此拋出異常。

4.2 元素的比較

4.2.1基本元素的比較

在Java中，基本類型的對象可以直接比較大小。

public class TestCompare {
  public static void main(String[] args) {
    int a = 10;
    int b = 20;
    System.out.println(a > b);
    System.out.println(a < b);
    System.out.println(a == b);
    char c1 = 'A';
    char c2 = 'B';
    System.out.println(c1 > c2);
    System.out.println(c1 < c2);
    System.out.println(c1 == c2);
    boolean b1 = true;
    boolean b2 = false;
    System.out.println(b1 == b2);
    System.out.println(b1 != b2);
 }
}

4.2.2 對象比較的問題

4.2.2.1 equals

class Card {
  public int rank; // 數(shù)值
  public String suit; // 花色
  public Card(int rank, String suit) {
    this.rank = rank;
    this.suit = suit;
 }
}
public class TestPriorityQueue {
  public static void main(String[] args) {
    Card c1 = new Card(1, "?");
    Card c2 = new Card(2, "?");
    Card c3 = c1;
    //System.out.println(c1 > c2);  // 編譯報錯
    System.out.println(c1 == c2);  // 編譯成功 ----> 打印false，因為c1和c2指向的是不同對象
    //System.out.println(c1 < c2);  // 編譯報錯
    System.out.println(c1 == c3);  // 編譯成功 ----> 打印true，因為c1和c3指向的是同一個對象
 }
}

c1、c2和c3分別是Card類型的引用變量，上述代碼在比較編譯時：

• c1 > c2 編譯失敗
• c1== c2 編譯成功
• c1 < c2 編譯失敗

從編譯結(jié)果可以看出，Java中引用類型的變量不能直接按照 > 或者 < 方式進(jìn)行比較。 那為什么== 可以比較？

因為：對于用戶實現(xiàn)自定義類型，都默認(rèn)繼承自O(shè)bject類，而Object類中提供了equal方法，而 == 默認(rèn)情況下調(diào)用的就是equal方法.

但是該方法的比較規(guī)則是：沒有比較引用變量引用對象的內(nèi)容，而是直接比較引用變量的地址，但有些情況下該種比較就不符合題意。

// Object中equal的實現(xiàn)，可以看到：直接比較的是兩個引用變量的地址
public boolean equals(Object obj) {
  return (this == obj);
}

有些情況下，需要比較的是對象中的內(nèi)容，比如：向優(yōu)先級隊列中插入某個對象時，需要對按照對象中內(nèi)容來調(diào)整堆，那該如何處理呢？答案是重寫覆蓋基類的equals

public class Card {
  public int rank; // 數(shù)值
  public String suit; // 花色
 
  public Card(int rank, String suit) {
    this.rank = rank;
    this.suit = suit;
 }
 
  @Override
  public boolean equals(Object o) {
    // 自己和自己比較
    if (this == o) {
      return true;
   }
   
    // o如果是null對象，或者o不是Card的子類
    if (o == null || !(o instanceof Card)) {
      return false;
   }
   
    // 注意基本類型可以直接比較，但引用類型最好調(diào)用其equal方法
    Card c = (Card)o;
    return rank == c.rank
      && suit.equals(c.suit);
      }
}

注意： 一般覆寫 equals 的套路就是上面演示的

1. 如果指向同一個對象，返回 true
2. 如果傳入的為 null，返回 false
3. 如果傳入的對象類型不是 Card，返回 false
4. 按照類的實現(xiàn)目標(biāo)完成比較，例如這里只要花色和數(shù)值一樣，就認(rèn)為是相同的牌
5. 注意下調(diào)用其他引用類型的比較也需要 equals，例如這里的 suit 的比較

覆寫基類equal的方式雖然可以比較，但缺陷是：equal只能按照相等進(jìn)行比較，不能按照大于、小于的方式進(jìn)行比較。

4.2.2.2 Comparble接口

Comparble是JDK提供的泛型的比較接口類，源碼實現(xiàn)具體如下：

public interface Comparable<E> {
  // 返回值:
  // < 0: 表示 this 指向的對象小于 o 指向的對象
  // == 0: 表示 this 指向的對象等于 o 指向的對象
  // > 0: 表示 this 指向的對象大于 o 指向的對象
  int compareTo(E o);
}

對用用戶自定義類型，如果要想按照大小與方式進(jìn)行比較時：在定義類時，實現(xiàn)Comparble接口即可，然后在類中重寫compareTo方法。

Java中的Comparable接口是用于實現(xiàn)對象的自然排序的接口。它包含一個compareTo方法，用于比較兩個對象的順序。

compareTo方法有以下三種返回值：

• 如果當(dāng)前對象小于被比較對象，則返回一個負(fù)整數(shù)。
• 如果當(dāng)前對象等于被比較對象，則返回0。
• 如果當(dāng)前對象大于被比較對象，則返回一個正整數(shù)。

下面是一個簡單的例子，演示如何使用Comparable接口來自然排序自定義的Person類：

import java.util.ArrayList;
import java.util.Collections;

class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // 實現(xiàn)compareTo方法
    @Override
    public int compareTo(Person other) {
        return this.age - other.age; // 按照年齡排序
    }

    // 其他getter和setter方法

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Person> people = new ArrayList<>();
        people.add(new Person("Alice", 25));
        people.add(new Person("Bob", 20));
        people.add(new Person("Charlie", 30));

        System.out.println("排序前:");
        for (Person person : people) {
            System.out.println(person);
        }

        Collections.sort(people); // 使用Collections.sort()方法進(jìn)行排序時，會自動調(diào)用compareTo()方法進(jìn)行比較

        System.out.println("排序后:");
        for (Person person : people) {
            System.out.println(person);
        }
    }
}

輸出結(jié)果：

排序前:
Person{name='Alice', age=25}
Person{name='Bob', age=20}
Person{name='Charlie', age=30}
排序后:
Person{name='Bob', age=20}
Person{name='Alice', age=25}
Person{name='Charlie', age=30}

在上面的代碼中，我們定義了一個Person類，并實現(xiàn)了Comparable接口。我們通過compareTo方法比較了兩個Person對象的年齡，并在Main類中使用Collections.sort方法對people列表進(jìn)行了排序。排序后，列表中的Person對象按照年齡的升序排列。

注意：Compareble是java.lang中的接口類，可以直接使用。

4.2.2.3 基于比較器比較

在Java中，如果我們想要比較兩個對象，并根據(jù)它們的屬性值進(jìn)行排序或判斷它們的相對順序，我們可以使用比較器（Comparator）進(jìn)行操作。

比較器是一個用于定義對象之間比較行為的接口。它包含了一個用于比較兩個對象的方法 - compare()。該方法接受兩個參數(shù)，分別是要比較的兩個對象，然后返回一個整數(shù)值來表示它們的相對順序。

下面是一個簡單的示例，展示如何使用比較器比較兩個Person對象：

import java.util.*;

// 定義Person類
class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // 省略其他屬性和方法

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

// 定義比較器類
class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person person1, Person person2) {
        if (person1.getAge() < person2.getAge()) {
            return -1; // person1在前
        } else if (person1.getAge() > person2.getAge()) {
            return 1; // person2在前
        } else {
            return 0; // 保持順序不變
        }
    }
}

public class Main {
    public static void main(String[] args) {
        // 創(chuàng)建Person對象
        Person person1 = new Person("Alice", 25);
        Person person2 = new Person("Bob", 30);
        Person person3 = new Person("John", 20);

        // 創(chuàng)建比較器對象
        AgeComparator comparator = new AgeComparator();

        // 使用比較器比較對象
        int result1 = comparator.compare(person1, person2); // 返回-1，person1在前
        int result2 = comparator.compare(person2, person1); // 返回1，person2在前
        int result3 = comparator.compare(person1, person3); // 返回0，保持順序不變

        System.out.println(result1);//-1
        System.out.println(result2);//1
        System.out.println(result3);//0
    }
}

在上述代碼中，我們定義了一個Person類，其中包含了姓名（name）和年齡（age）屬性。然后，我們創(chuàng)建了一個比較器類AgeComparator，實現(xiàn)了Comparator接口，并重寫了compare()方法來根據(jù)年齡來判斷相對順序。

在main()方法中，我們創(chuàng)建了三個Person對象，并使用AgeComparator比較器對象來比較它們的年齡。最后，我們打印了比較的結(jié)果，驗證了對象之間的比較行為。

注意：Comparator是java.util 包中的泛型接口類，使用時必須導(dǎo)入對應(yīng)的包。

我們要注意區(qū)分Comparable和Comparato：

• 實現(xiàn)Comparable接口，重寫compareTo方法
• 實現(xiàn)Comparator接口，重寫compare方法

三種比較方式對比：文章來源地址http://www.zghlxwxcb.cn/news/detail-717708.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) - 6（優(yōu)先級隊列（堆）13000字詳解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！