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