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