、二叉樹的次序存儲

1.堆的存儲方法

  使用數(shù)組保存二叉樹結(jié)構(gòu)，方法即將二叉樹用層序遍歷方法放入數(shù)組中。

  一般只適合表明徹底二叉樹，因為非徹底二叉樹會有空間的糟蹋。

這種方法的主要用法就是堆的表明。




2.下標關(guān)系

已知 雙親 (parent) 的下標，則：


左孩子(left)下標 = 2 * parent + 1;

右孩子(right)下標 = 2 * parent + 2;


已知孩子（不區(qū)別左右）(child)下標，則：


雙親(parent)下標 = (child - 1) / 2;


二、堆(heap)

1.概念

1.堆邏輯上是一棵徹底二叉樹

2.堆物理上是保存在數(shù)組中

3.滿意任意結(jié)點的值都大于其子樹中結(jié)點的值，叫做大堆，或許大根堆，或許最大堆

4.反之，則是小堆，或許小根堆，或許最小堆

5.堆的基本作用是，快速找集合中的最值


2.大/小 根堆

2.1小根堆


每棵樹的根節(jié)點都是小于孩子節(jié)點，此時這棵樹就叫做小根堆


2.2大根堆


每棵樹的根節(jié)點都是大于孩子節(jié)點的，此時這棵樹就叫做大根堆

  咱們在說 巨細根堆 時，只說了 根節(jié)點比孩子節(jié)點大，沒有說 左右孩子節(jié)點誰比誰大、誰比誰小.

所以得出結(jié)論

不管是 大根堆、仍是小根堆，左右孩子的巨細關(guān)系是不確定的，咱們只能確定根節(jié)點和孩子節(jié)點的關(guān)系.


3.建堆操作

  下面咱們給出一個數(shù)組，這個數(shù)組邏輯上能夠看做一顆徹底二叉樹，但是還不是一個堆，現(xiàn)在咱們通過算法，把它構(gòu)建成一個堆。


  根節(jié)點左右子樹不是堆，咱們怎么調(diào)整呢？這里咱們從倒數(shù)的第一個非葉子節(jié)點的子樹開端調(diào)整，一向調(diào)整到根節(jié)點的樹，就能夠調(diào)整成堆。


將一個二叉樹 調(diào)整為一個 大根堆





這棵二叉樹調(diào)整為 大根堆 必須將 每顆子樹都調(diào)整為大根堆.


3.1向下調(diào)整

思想 步驟：

parent —> 根節(jié)點下標

child —> 孩子節(jié)點下標


1.從最終一棵子樹進行調(diào)整.

2.每顆子樹從根節(jié)點向下調(diào)整，假如左右孩子節(jié)點的最大值比這個根節(jié)點大，那么值互換，然后 parent 指向 child ,child = 2* parent + 1， 繼續(xù)向下調(diào)整，直到 下標child 超出二叉樹 規(guī)模.

3.重復(fù)第二步的操作，遍歷每一顆子樹，直到所有子樹全部遍歷完結(jié).


代碼實現(xiàn)：





咱們對這個代碼進行測驗



測驗堆中的結(jié)果：


時間復(fù)雜度分析：


  粗略預(yù)算，能夠認為是在循環(huán)中執(zhí)行向下調(diào)整，為 O(n * log(n))（了解）實際上是 O(n)


堆排序中建堆過程時間復(fù)雜度O(n)怎么來的？




4.入隊操作

步驟

1.判斷是否滿容

2.在數(shù)組的最終插入元素

3.調(diào)整為 大/小 根堆


在這幾個步驟中，前兩步咱們都能夠完結(jié) ，第三步咱們要注意：


使用 向上調(diào)整 調(diào)整為大/ 小根堆


之前咱們介紹了 向下調(diào)整

這次咱們說的是向上調(diào)整，與之前向上調(diào)整的思路十分相似~~

咱們來說一下 向上調(diào)整的思路


4.1向上調(diào)整




4.2push 入隊的完好代碼展示




5.出隊操作

  為了避免破壞堆的結(jié)構(gòu)，刪去時并不是直接將堆頂元素刪去，而是用數(shù)組的最終一個元素與堆頂元素交流，然后通過向下調(diào)整方法重新調(diào)整成堆.


思路：


1.交流 數(shù)組首尾元素

2.usedSize- -,刪去最終的元素

3.使用向下調(diào)整 ，調(diào)整為大/小 根堆


5.1pop 出隊代碼徹底展示



6.檢查堆頂元素

回來 下標為0的數(shù)組元素.回來堆頂元素.





現(xiàn)在咱們來看一個 堆的 使用


7.TOK 問題

咱們在這里 提出一個問題：


在一千萬個數(shù)據(jù)中找到 前 10個最大的 數(shù)據(jù),請問如何查找

咱們有 幾個想法


1.基本反應(yīng)，給1000萬個數(shù)據(jù)排序，取10個最大 的，咱們直接 Arrays.sort () ;

  這種排序方法當然也不是不能夠，只不過時間復(fù)雜度非常大，在面試中寫出這樣的排序思路會落得劣勢.


2.將這1000個數(shù)據(jù) 建成一個大堆，每次將最大的取出，然后調(diào)整，取出10個即可.

  這種方法的缺陷則是， 堆太大了，咱們建立的堆也會是 1000萬，假如這個數(shù)據(jù)更大，那么堆也會更大，每次調(diào)整的復(fù)雜度也很大.


3.建立一個巨細為 K 的小堆.




以上面這個數(shù)組為例，找出這組數(shù)據(jù)中的前三個最大的元素.


3.1 將當時數(shù)據(jù)的前三個 建立為小堆

3.2 遍歷剩余的元素，順次和堆頂元素進行比較. 假如當時 i 下標元素 比堆頂元素大，就把i下標入隊.



  堆頂元素一定是最小的，每次都與堆頂元素進行比較，每次都將最小的那個除掉，最終遍歷完，剩余的就是 最大的幾個數(shù)據(jù)了嘛~

根據(jù)上面的這個 思路，咱們同理能夠解決許多相似的問題