java二叉堆
1. 【JDK源碼分析】Timer/TimerTask 源碼分析
在java中，Timer 類是實現定時任務的常見工具，配合TimerTask 實現定時、延遲或周期性執行。本文將深入剖析其源碼結構和工作原理。
Timer 的核心機制涉及關鍵類，包括TimerThread、Timer、TimerQueue 和 TimerTask。一個Timer 實例對應一個TimerThread，負責執行任務；Timer擁有一個TimerThread和一個TimerQueue，而TimerQueue中存儲了多個TimerTask。這樣的關系可以總結為：
- 1個 TimerThread -> 1個線程
- 1個 Timer -> 持有 TimerThread 和 TimerQueue
- 1個 TimerQueue -> 持有多個 TimerTask
源碼分析時，首先創建Timer時，thread和queue會在聲明時初始化為final類型，確保它們與Timer的生命周期綁定。接著，任務通過schele方法進行調度，這個過程會根據TimerTask類型設置不同的period參數。
TimerTask 是一個實現了Runnable介面的抽象類，子類需實現run方法。TimerTask的類型決定了其執行周期。TimerThread的run方法包含一個死循環，類似Android的Handler機制。
TimerQueue作為隊列，內部使用完全二叉樹結構，add和fixUp方法用於維護最小執行時間的節點在隊列前端。purge方法執行後，會調用fixDown方法進行調整。
總之，每個Timer實例由一個線程和一個二叉堆（通過TimerQueue實現）組成，用於管理定時任務的執行順序。理解這些核心組件的交互，有助於深入理解Timer的工作機制。
2. 看圖說話之二叉堆(優先隊列)——原理解析
優先隊列更多的是一種邏輯上和業務上的設計。隊列中的每項元素都分配一個優先權值，隊列的出隊順序按照優先權值來劃分，高優先權先出隊或者低優先權先出隊。這樣一個優先隊列必須具備兩個最基本的操作——入隊，以及高(低)優先權出隊。優先隊列在很多場景中都有運用，比如列印機的任燃答段務調度和操作系統中的進程調度都有用到優先隊列的設計。
此時我們假設並不知道有堆這樣的數據結構，想實現上述這樣的功能，其實也可以有多種解決方案，比如以下兩種：
二叉堆如其名字一樣和二叉樹具有緊密的關系。二叉堆是一種特殊的二叉樹，是對一般的二叉樹提出了結構性和堆序性的要求，這種特殊結構性和堆序性是二叉堆的性質所在。
1.結構性：二叉堆是一個完全二叉樹
2.堆序性：所有的節點值均小於(大於)其後裔節點值，若所有節點值大於其後裔節點這樣的二叉堆稱為大根堆##點值均小於其後裔節點這樣的二叉堆成為小根堆。
這里可以看到，假如是小根堆的情況，那麼每次取堆頂的元素，就完成了按低優先順序出隊的功能。若是大根隊取堆頂的元素則完成按高優舉嫌先級出對的順序。
這里需要特別注意就是，每次的出隊操作=返回堆頂元素+刪除堆頂元素，每次刪除堆頂元素之後，需要保證依舊滿足二叉堆的結構性和對堆序性，這個刪除和調整的過程稱為堆調整。
下面以大根堆為例進行介紹一次堆調整，並且分析其時間復雜度為什麼是O(logN)。下文描述中，堆的刪除操作=優先隊列的出隊，堆的插入操作=優先隊列的入隊。
上文介紹了大根堆的出隊操作，其時間復雜度在O(logN),此處介紹大根堆的入隊操作，入隊操作和出隊操作和其相似，最壞時間復雜度也是O(logN)。下面將通過圖例的形式分析大根堆的入隊操作，假設插入元素是19。
2.如圖9所示，皮譽在插入元素之後二叉堆的結構特性已經滿足了，下面主要需要調整堆序特性。對於元素19而言，找到其父親元素8，判斷堆序性，發現19大於8，所以交換19和8的位置，結果如下。
Reference:
[1] 數據結構與演算法 java語言描述版
[2] 博客原文
3. Java中堆和棧創建對象的區別
堆和棧是信息學數據結構通用名詞，不僅在Java中，C++里也有調用模板。
堆(heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：
堆中某個節點的值總是不大於或不小於其父節點的值；
堆總是一棵完全樹。
將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。
堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關系時，稱之為堆。
(ki
<=
k2i,ki
<=
k2i+1)或者(ki
>=
k2i,ki
>=
k2i+1),
(i
=
1,2,3,4...n/2)
若將和此次序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。
4. java中都有哪些數據結構
數據結構：
①數組 (Array)
在程序設計中，為了處理方便， 把具有相同類型的若干變數按有序的形式組織起來。這些按序排列的同類數
據元素的集合稱為數組。在C語言中， 數組屬於構造數據類型。一個數組可以分解為多個數組元素，這些數組
元素可以是基本數據類型或是構造類型。因此按數組元素的類型不同，數組又可分為數值數組、字元數組、指
針數組、結構數組等各種類別。
②棧 (Stack)
棧是只能在某一端插入和刪除的特殊線性表。它按照先進後出的原則存儲數據，先進入的數據被壓入棧底，最後
的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。
③隊列 (Queue)
一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作。進行
插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。
④鏈表 (Linked List)
一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：
一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。
⑤樹 (Tree)
樹是包含n（n>0）個結點的有窮集合K，且在K中定義了一個關系N，N滿足 以下條件：
（1）有且僅有一個結點 k0，他對於關系N來說沒有前驅，稱K0為樹的根結點。簡稱為根（root）
（2）除K0外，k中的每個結點，對於關系N來說有且僅有一個前驅。
（3）K中各結點，對關系N來說可以有m個後繼（m>=0）。
⑥堆 (Heap)
在計算機科學中，堆是一種特殊的樹形數據結構，每個結點都有一個值。通常我們所說的堆的數據結構，是指
二叉堆。堆的特點是根結點的值最小（或最大），且根結點的兩個子樹也是一個堆。
⑦圖 (Graph)
圖是由結點的有窮集合V和邊的集合E組成。其中，為了與樹形結構加以區別，在圖結構中常常將結點稱為頂點，
邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關系。
⑧散列表 (Hash)
若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱
這個對應關系f為散列函數(Hash function)，按這個思想建立的表為散列表。
差不多我就知道這些了~
5. java在存儲數組時棧內存和堆內存的聯系是什麼
堆和棧都是一種數據項按序排列的數據結構。
（1）棧就像裝數據的桶或箱子：它是一種具有後進先出性質的數據結構，也就是說後存放的先取，先存放的後取。這就如同要取出放在箱子裡面底下的東西（放入的比較早的物體），首先要移開壓在它上面的物體（放入的比較晚的物體）。
（2）堆像一棵倒過來的樹：堆是一種經過排序的樹形數據結構，每個結點都有一個值。通常所說的堆的數據結構，是指二叉堆。堆的特點是根結點的值最小（或最大），且慎敗飢根結點的寬返兩個子樹也是一個堆。由於堆的這個特性，常用來實現優先隊列，堆的存取是隨意，這就如同在圖書館的書架上取書，雖然書的擺放是有順序的，但是想取任意一本時不必像棧一樣，先取出前面所有的書，書架這枯運種機制不同於箱子，可以直接取出想要的書。