文章目錄
- 一、二叉樹的順序存盤
- 1.堆的存盤方式
- 2.下標關系
- 二、堆(heap)
- 1.概念
- 2.大/小 根堆
- 2.1小根堆
- 2.2大根堆
- 3.建堆操作
- 3.1向下調整
- 4.入隊操作
- 4.1向上調整
- 4.2push 入隊的完整代碼展示
- 5.出隊操作
- 5.1pop 出隊代碼完全展示
- 6.查看堆頂元素
- 7.TOK 問題
- 7.1TOPK
- 8.堆排序
- 未完待續~~
文章內容介紹大綱
一、二叉樹的順序存盤
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下標入隊.
??堆頂元素一定是最小的，每次都與堆頂元素進行比較，每次都將最小的那個剔除，最后遍歷完，剩下的就是 最大的幾個資料了嘛~
根據上面的這個 思路，我們同理可以解決很多類似的問題
7.1TOPK
找到一組資料中 最大的K個資料
建立 大小為 K 的小堆，依次遍歷，最后堆中的資料 即為結果.
找到一組資料中 第K大的資料
建立 大小為 K 的小堆，依次遍歷，最后堆頂元素 即為結果.
找到一組資料中 最小的K個資料
建立 大小為 K 的大堆，依次遍歷，最后堆中的資料 即為結果.
找到一組資料中 第K小的資料
建立 大小為 K 的大堆，依次遍歷，最后堆頂元素 即為結果.
8.堆排序
從小到大排序 —— 升序 建立大堆
從大到小排序 —— 降序 建立小堆
思路： 以升序 為 例
1.交換 陣列 首尾 的元素，這樣最大的堆頂元素 被放在陣列的最后一個，此時 最后一個元素 已經定好序了.
2.此時從第一個到 倒數第二個再次調整，調整完后將堆頂元素 與倒數第二個元素交換，按照這樣的邏輯規律，回圈直到 有序.
我們以實際 例子說明…
1.首尾交換
2.向下調整
重復此操作直到全部有序
演算法演示：
代碼實作：
我們看一下排序的結果：
說明我們 堆排序成功運行~~
好了，堆的知識先講到這里，希望大家多多練習~~
?下節就是關于Java中堆的使用的知識及練習了，大家敬請期待~~
Java集合與資料結構——優先級佇列的使用及練習
未完待續~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/293953.html
標籤：java