文章內(nèi)容介紹大綱

一、二叉樹的順序存儲(chǔ)

1.堆的存儲(chǔ)方式

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

一般只適合表示完全二叉樹，因?yàn)榉峭耆鏄鋾?huì)有空間的浪費(fèi)。

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

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.堆邏輯上是一棵完全二叉樹

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

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

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

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

2.大/小 根堆

2.1小根堆

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

2.2大根堆

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

  我們?cè)谡f(shuō) 大小根堆 時(shí)，只說(shuō)了 根節(jié)點(diǎn)比孩子節(jié)點(diǎn)大，沒(méi)有說(shuō) 左右孩子節(jié)點(diǎn)誰(shuí)比誰(shuí)大、誰(shuí)比誰(shuí)小.

所以得出結(jié)論

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

3.建堆操作

  下面我們給出一個(gè)數(shù)組，這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個(gè)堆，現(xiàn)在我們通過(guò)算法，把它構(gòu)建成一個(gè)堆。

  根節(jié)點(diǎn)左右子樹不是堆，我們?cè)趺凑{(diào)整呢？這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹開始調(diào)整，一直調(diào)整到根節(jié)點(diǎn)的樹，就可以調(diào)整成堆。

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

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

3.1向下調(diào)整

思想 步驟：

parent —> 根節(jié)點(diǎn)下標(biāo)

child —> 孩子節(jié)點(diǎn)下標(biāo)

1.從最后一棵子樹進(jìn)行調(diào)整.

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

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

代碼實(shí)現(xiàn)：

我們對(duì)這個(gè)代碼進(jìn)行測(cè)試

測(cè)試堆中的結(jié)果：

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

  粗略估算，可以認(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è)步驟中，前兩步我們都可以完成 ，第三步我們要注意：

利用 向上調(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.查看堆頂元素

返回 下標(biāo)為0的數(shù)組元素.返回堆頂元素.

現(xiàn)在我們來(lái)看一個(gè) 堆的 應(yīng)用

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ì)落得下風(fēng).

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

  這種方法的缺點(diǎn)則是， 堆太大了，我們建立的堆也會(huì)是 1000萬(wàn)，如果這個(gè)數(shù)據(jù)更大，那么堆也會(huì)更大，每次調(diào)整的復(fù)雜度也很大.

3.建立一個(gè)大小為 K 的小堆.

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

3.1 將當(dāng)前數(shù)據(jù)的前三個(gè) 建立為小堆

3.2 遍歷剩下的元素，依次和堆頂元素進(jìn)行比較. 如果當(dāng)前 i 下標(biāo)元素 比堆頂元素大，就把i下標(biāo)入隊(duì).

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

根據(jù)上面的這個(gè) 思路，我們同理可以解決很多類似的問(wèn)題

7.1TOPK

找到一組數(shù)據(jù)中 最大的K個(gè)數(shù)據(jù)

建立 大小為 K 的小堆，依次遍歷，最后堆中的數(shù)據(jù) 即為結(jié)果.

找到一組數(shù)據(jù)中 第K大的數(shù)據(jù)

建立 大小為 K 的小堆，依次遍歷，最后堆頂元素 即為結(jié)果.

找到一組數(shù)據(jù)中 最小的K個(gè)數(shù)據(jù)

建立 大小為 K 的大堆，依次遍歷，最后堆中的數(shù)據(jù) 即為結(jié)果.

找到一組數(shù)據(jù)中 第K小的數(shù)據(jù)

建立 大小為 K 的大堆，依次遍歷，最后堆頂元素 即為結(jié)果.

8.堆排序

從小到大排序 —— 升序 建立大堆

從大到小排序 —— 降序 建立小堆

思路： 以升序 為 例

1.交換 數(shù)組 首尾 的元素，這樣最大的堆頂元素 被放在數(shù)組的最后一個(gè)，此時(shí) 最后一個(gè)元素 已經(jīng)定好序了.

2.此時(shí)從第一個(gè)到 倒數(shù)第二個(gè)再次調(diào)整，調(diào)整完后將堆頂元素 與倒數(shù)第二個(gè)元素交換，按照這樣的邏輯規(guī)律，循環(huán)直到 有序.

我們以實(shí)際 例子說(shuō)明…

1.首尾交換

2.向下調(diào)整

重復(fù)此操作直到全部有序

算法演示：

代碼實(shí)現(xiàn)：

我們看一下排序的結(jié)果：

說(shuō)明我們 堆排序成功運(yùn)行~~

好了，堆的知識(shí)先講到這里，希望大家多多練習(xí)~~

下節(jié)就是關(guān)于Java中堆的使用的知識(shí)及練習(xí)了，大家敬請(qǐng)期待~~

到此這篇關(guān)于java數(shù)據(jù)結(jié)構(gòu)-堆實(shí)現(xiàn)優(yōu)先隊(duì)列的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論