、二叉樹(shù)的次序存儲
1.堆的存儲方法
使用數組保存二叉樹(shù)結構，方法即将二叉樹(shù)用層序遍曆方法放(fàng)入數組中(zhōng)。
一(yī)般隻适合表明徹底二叉樹(shù)，因爲非徹底二叉樹(shù)會有空間的糟蹋。
這種方法的主要用法就是堆的表明。
2.下(xià)标關系
已知(zhī) 雙親 (parent) 的下(xià)标，則：
左孩子(left)下(xià)标 = 2 * parent + 1;
右孩子(right)下(xià)标 = 2 * parent + 2;
已知(zhī)孩子（不區别左右）(child)下(xià)标，則：
雙親(parent)下(xià)标 = (child - 1) / 2;
二、堆(heap)
1.概念
1.堆邏輯上是一(yī)棵徹底二叉樹(shù)
2.堆物(wù)理上是保存在數組中(zhōng)
3.滿意任意結點的值都大(dà)于其子樹(shù)中(zhōng)結點的值，叫做大(dà)堆，或許大(dà)根堆，或許最大(dà)堆
4.反之，則是小(xiǎo)堆，或許小(xiǎo)根堆，或許最小(xiǎo)堆
5.堆的基本作用是，快速找集合中(zhōng)的最值
2.大(dà)/小(xiǎo) 根堆
2.1小(xiǎo)根堆
每棵樹(shù)的根節點都是小(xiǎo)于孩子節點，此時這棵樹(shù)就叫做小(xiǎo)根堆
2.2大(dà)根堆
每棵樹(shù)的根節點都是大(dà)于孩子節點的，此時這棵樹(shù)就叫做大(dà)根堆
咱們在說 巨細根堆 時，隻說了 根節點比孩子節點大(dà)，沒有說 左右孩子節點誰比誰大(dà)、誰比誰小(xiǎo).
所以得出結論
不管是 大(dà)根堆、仍是小(xiǎo)根堆，左右孩子的巨細關系是不确定的，咱們隻能确定根節點和孩子節點的關系.
3.建堆操作
下(xià)面咱們給出一(yī)個數組，這個數組邏輯上能夠看做一(yī)顆徹底二叉樹(shù)，但是還不是一(yī)個堆，現在咱們通過算法，把它構建成一(yī)個堆。
根節點左右子樹(shù)不是堆，咱們怎麽調整呢？這裏咱們從倒數的第一(yī)個非葉子節點的子樹(shù)開(kāi)端調整，一(yī)向調整到根節點的樹(shù)，就能夠調整成堆。
将一(yī)個二叉樹(shù) 調整爲一(yī)個 大(dà)根堆
這棵二叉樹(shù)調整爲 大(dà)根堆 必須将 每顆子樹(shù)都調整爲大(dà)根堆.
3.1向下(xià)調整
思想 步驟：
parent —> 根節點下(xià)标
child —> 孩子節點下(xià)标
1.從最終一(yī)棵子樹(shù)進行調整.
2.每顆子樹(shù)從根節點向下(xià)調整，假如左右孩子節點的最大(dà)值比這個根節點大(dà)，那麽值互換，然後 parent 指向 child ,child = 2* parent + 1， 繼續向下(xià)調整，直到 下(xià)标child 超出二叉樹(shù) 規模.
3.重複第二步的操作，遍曆每一(yī)顆子樹(shù)，直到所有子樹(shù)全部遍曆完結.
代碼實現：
咱們對這個代碼進行測驗
測驗堆中(zhōng)的結果：
時間複雜(zá)度分(fēn)析：
粗略預算，能夠認爲是在循環中(zhōng)執行向下(xià)調整，爲 O(n * log(n))（了解）實際上是 O(n)
堆排序中(zhōng)建堆過程時間複雜(zá)度O(n)怎麽來的？
4.入隊操作
步驟
1.判斷是否滿容
2.在數組的最終插入元素
3.調整爲 大(dà)/小(xiǎo) 根堆
在這幾個步驟中(zhōng)，前兩步咱們都能夠完結 ，第三步咱們要注意：
使用 向上調整 調整爲大(dà)/ 小(xiǎo)根堆
之前咱們介紹了 向下(xià)調整
這次咱們說的是向上調整，與之前向上調整的思路十分(fēn)相似~~
咱們來說一(yī)下(xià) 向上調整的思路
4.1向上調整
4.2push 入隊的完好代碼展示
5.出隊操作
爲了避免破壞堆的結構，删去(qù)時并不是直接将堆頂元素删去(qù)，而是用數組的最終一(yī)個元素與堆頂元素交流，然後通過向下(xià)調整方法重新調整成堆.
思路：
1.交流 數組首尾元素
2.usedSize- -,删去(qù)最終的元素
3.使用向下(xià)調整 ，調整爲大(dà)/小(xiǎo) 根堆
5.1pop 出隊代碼徹底展示
6.檢查堆頂元素
回來 下(xià)标爲0的數組元素.回來堆頂元素.
現在咱們來看一(yī)個 堆的 使用
7.TOK 問題
咱們在這裏 提出一(yī)個問題：
在一(yī)千萬個數據中(zhōng)找到 前 10個最大(dà)的 數據,請問如何查找
咱們有 幾個想法
1.基本反應，給1000萬個數據排序，取10個最大(dà) 的，咱們直接 Arrays.sort () ;
這種排序方法當然也不是不能夠，隻不過時間複雜(zá)度非常大(dà)，在面試中(zhōng)寫出這樣的排序思路會落得劣勢.
2.将這1000個數據 建成一(yī)個大(dà)堆，每次将最大(dà)的取出，然後調整，取出10個即可.
這種方法的缺陷則是， 堆太大(dà)了，咱們建立的堆也會是 1000萬，假如這個數據更大(dà)，那麽堆也會更大(dà)，每次調整的複雜(zá)度也很大(dà).
3.建立一(yī)個巨細爲 K 的小(xiǎo)堆.
以上面這個數組爲例，找出這組數據中(zhōng)的前三個最大(dà)的元素.
3.1 将當時數據的前三個 建立爲小(xiǎo)堆
3.2 遍曆剩餘的元素，順次和堆頂元素進行比較. 假如當時 i 下(xià)标元素 比堆頂元素大(dà)，就把i下(xià)标入隊.
堆頂元素一(yī)定是最小(xiǎo)的，每次都與堆頂元素進行比較，每次都将最小(xiǎo)的那個除掉，最終遍曆完，剩餘的就是 最大(dà)的幾個數據了嘛~
根據上面的這個 思路，咱們同理能夠解決許多相似的問題
