資訊專欄INFORMATION COLUMN
摘要：模型優(yōu)先隊(duì)列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)以及找出返回并刪除優(yōu)先隊(duì)列中最小的元素。左式堆也是二叉樹，左式堆和二叉堆的唯一區(qū)別是左式堆不是理想平衡，而實(shí)際上趨向于非常不平衡。事實(shí)上，沿左式堆的右路徑是該堆中的最短路徑。
6.1 模型
優(yōu)先隊(duì)列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)：insert 以及 deleteMin（找出、返回并刪除優(yōu)先隊(duì)列中最小的元素）。
insert 操作等價(jià)于 enqueue（入隊(duì)），而 deleteMin 則是運(yùn)算 dequeue（出隊(duì))在優(yōu)先隊(duì)列中的等價(jià)操作。
一些簡單的實(shí)現(xiàn)可以使用簡單鏈表進(jìn)行不排序的插入，則插入操作為 O(1)，但是刪除需要遍歷鏈表為 O(N)。
另一種方法是讓鏈表保持排序狀態(tài)：插入代價(jià)高昂 O(N)，但刪除為 O(1).但是 deleteMin 的操作比插入操作少，前者可能更好。
另外一種方法是使用二叉查找樹，它對這兩種操作的平均運(yùn)行時(shí)間都為 O(log N)。
但是，由于我們刪除的唯一元素是最小元，反復(fù)出去左子樹的節(jié)點(diǎn)會(huì)損害樹的平衡使得右子樹加重，在最壞情況下 deleteMin 將左子樹刪空。
另外，使用查找樹有很多我們數(shù)據(jù)結(jié)構(gòu)不需要的鏈。
二叉堆我們將要使用的數(shù)據(jù)結(jié)構(gòu)叫做二叉堆（binary heap），它的使用對于優(yōu)先隊(duì)列的實(shí)現(xiàn)相當(dāng)普遍，以至于堆（heap）這個(gè)詞不加修飾的用在優(yōu)先隊(duì)列的上下文中時(shí)，一般都是指數(shù)據(jù)結(jié)構(gòu)的這種實(shí)現(xiàn)。
二叉堆有兩個(gè)性質(zhì)：結(jié)構(gòu)性和堆序性。
結(jié)構(gòu)性質(zhì)堆是一棵被完全填滿的二叉樹，有可能的例外是在底層，底層上的元素從左到右填入。這樣的樹被稱為完全二叉樹（complete binary tree）。
一棵高為 h 的完全二叉樹有 2h 到 2h+1 - 1 個(gè)節(jié)點(diǎn)。它的高度為 Log N，顯然它是 O(log N)。
因?yàn)槎娑咽菨M二叉樹，所以在高度為 h-1 的樹包含
20 + ... + 2h-1 = 2h -1 個(gè)元素，
在高度為 h 的層上有 1 至 2h 個(gè)元素，所以應(yīng)該有 2h 至 2h+1 - 1 個(gè)元素。
因?yàn)橥耆鏄溥@么有規(guī)律，所以它可以用一個(gè)數(shù)組表示而不需要使用鏈。
對于數(shù)組中任意位置 i 上的元素，其左兒子在位置 2i 上，右兒子在左兒子后的單元 (2i + 1)上。它的父親則在位置 [i / 2] 上。
堆序性質(zhì)讓操作快速執(zhí)行的性質(zhì)是堆序性質(zhì)（heap-order property）。由于我們想要快速找出最小元，因此最小的元應(yīng)該在根上。如果我們考慮任意子樹也應(yīng)該是一個(gè)堆，那么任意節(jié)點(diǎn)就給應(yīng)該小于它的所有后裔。
基本的堆操作 insert（插入）為了將一個(gè)元素 X 插入到堆中，我們在下一個(gè)可用位置創(chuàng)建一個(gè)空穴，否則該堆將不是完全樹。如果 X 可以放在該空穴中而并不破壞對的序，那么插入完成。
否則，我們把空穴的父節(jié)點(diǎn)移入該空穴中，這樣空穴就朝著根的方向上冒一步。繼續(xù)該過程直到 X 能夠放入空穴中為止。
如下圖所示：為了插入 14，我們在堆的下一個(gè)可用位置上建立一個(gè)空穴，由于將 14 插入空穴破壞了堆序性質(zhì)，因此將 31 移入該空穴。
在圖中，將元素從做到右執(zhí)行插入，所以下一個(gè)空穴的位置應(yīng)該在 31 的右節(jié)點(diǎn)上。
當(dāng)刪除一個(gè)最小元是，要在根節(jié)點(diǎn)建立一個(gè)空穴。由于現(xiàn)在少了一個(gè)元素，因此堆中最后一個(gè)元素 X 必須移動(dòng)帶該堆的某個(gè)地方。這是為了滿足二叉堆的結(jié)構(gòu)性質(zhì) -- 它是一棵完全二叉樹，空穴只能在最后一層的最后一個(gè)元素之后
因此，我們將空穴的兩個(gè)兒子中較小者移入空穴這樣就把空穴向下推了一層。
重復(fù)該步驟直到 X 可以被放入空穴中。
例如，對于下面的例子中，我們先刪除元素 13，這將在二叉堆的根節(jié)點(diǎn)上建立一個(gè)空穴。隨后往里面插入數(shù)字 31.
在堆的實(shí)現(xiàn)中經(jīng)常發(fā)生的錯(cuò)誤是當(dāng)堆中存在偶數(shù)個(gè)元素的時(shí)候，可能會(huì)遇到某個(gè)節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)的情況（只會(huì)在最下層出現(xiàn)）。
package com.mosby.ch06; /** * @author dhy */ public class BinaryHeap左式堆> { public BinaryHeap(){ this(DEFAULT_CAPACITY); } public BinaryHeap(int capacity){ currentSize = 0; array = new Comparable[capacity]; } /** * 向堆插入一個(gè)元素
* ** * 在這里我們的代碼使用了一個(gè)小技巧：我們現(xiàn)在的目的是要將當(dāng)前堆中的空穴（初始為數(shù)組中最后一個(gè)元素之后） * 移動(dòng)到一個(gè)滿足將 X 插入該空穴后不影響堆的性質(zhì)的位置。* * @param x */ public void insert(T x){ //因?yàn)槎褍?nèi)部的數(shù)組實(shí)現(xiàn)的第一個(gè)元素是空 if(currentSize == array.length - 1){ enlargeArray(array.length * 2 + 1); } //當(dāng)前空穴的位置在最后一個(gè)元素的后一位，同時(shí)插入空穴之后 currentSize 增加一。等同于下面的代碼 //int hole = currentSize + 1; //currentSize++; int hole = ++currentSize; for(; hole > 1 && x.compareTo((T) array[hole / 2]) < 0; hole /= 2){ array[hole] = array[hole / 2]; } array[hole] = x; } public T findMin(){ if(isEmpty()){ return null; } return (T) array[1]; } public T deleteMin(){ if(isEmpty()){ throw new RuntimeException("Under flow"); } T minItem = findMin(); array[1] = array[currentSize--]; percolateDown(1); return minItem; } public boolean isEmpty(){ return currentSize == 0; } public void makeEmpty(){ currentSize = 0; } private static final int DEFAULT_CAPACITY = 100; private int currentSize;//當(dāng)前堆中元素個(gè)數(shù) private Comparable[] array;//堆內(nèi)部的以數(shù)組的形式存放 /** * 對空穴進(jìn)行下濾 * @param hole */ private void percolateDown(int hole){ //這里 child 的初值不會(huì)影響程序的正確性，但是 eclipse 的編譯器有 bug， int child; 是無法通過編譯的 //在 IDEA 下可以直接 int child; int child = hole * 2; Comparable tmp = array[hole]; /** * 這里注意一點(diǎn)，hole * 2 <= currentSize，因?yàn)閿?shù)組的第一個(gè)元素為空
* * 如果我們每次都將當(dāng)前空穴的位置和它的父元素交換，那么對于一個(gè)元素上濾 d 層， * 那么由于交換而執(zhí)行的賦值次數(shù)就是 3d。
* * 而這里，我們每次只是在滿足條件時(shí)將父節(jié)點(diǎn)的值賦給了這個(gè)空穴而沒有將空穴的值上濾。
* 這樣上濾 d 層將只需要 d 次對空穴的賦值和一次最后將 X 插入的賦值?？偣?d+1 次賦值。 * *
* 數(shù)組中的實(shí)際元素應(yīng)該是 array[i] - array[currentSize] */ for(; hole * 2 <= currentSize; hole = child){ child = hole * 2; /** * 在下濾的過程中，我們每次將當(dāng)前節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)中較小的那個(gè)子節(jié)點(diǎn)跟空穴交換
* * 但是這必須要考慮一個(gè)問題，在最下層的時(shí)候，可能會(huì)有某個(gè)節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)
* * 而在非最下層則不會(huì)有這個(gè)問題，因?yàn)槎娑咽且粋€(gè)完全二叉樹。
* * 而根據(jù)二叉堆的插入性質(zhì)（從左往右插入），那么只有一個(gè)元素的節(jié)點(diǎn)，這個(gè)元素的子節(jié)點(diǎn)肯定 * 就是二叉堆的最后一個(gè)節(jié)點(diǎn)。此時(shí) hole == currentSize. */ if(child != currentSize && array[child + 1].compareTo((T) array[child]) < 0){ child++; } if(array[child].compareTo((T) tmp) < 0){ array[hole] = array[child]; }else{ break; } } array[hole] = tmp; } /** * 如果提供了通過數(shù)組初始化二叉堆的方式，那么在傳入一個(gè)數(shù)組后調(diào)用該方法即可得到一個(gè)二叉堆。 */ private void buildHeap(){ for(int i = currentSize / 2; i > 0; i--){ percolateDown(i); } } public void enlargeArray(int newSize){ Comparable[] newArray = new Comparable[newSize]; for(int i = 1; i <= currentSize; i++){ newArray[i] = array[i]; } array = newArray; } public int size(){ return currentSize; } }
設(shè)計(jì)一種堆結(jié)構(gòu)像二叉堆那樣有效的支持合并操作（即以 O(N) 時(shí)間處理一個(gè) merge）而且只使用一個(gè)數(shù)組似乎很困難。原因在于，合并似乎需要把一個(gè)數(shù)組拷貝到另外一個(gè)數(shù)組中去。
正因?yàn)槿绱?，所有支持有效合并的高?jí)數(shù)據(jù)結(jié)構(gòu)都需要使用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)
左式堆 （leftist heap）像二叉堆一樣具有結(jié)構(gòu)性和有序性。左式堆也是二叉樹，左式堆和二叉堆的唯一區(qū)別是：左式堆不是理想平衡（perfectly balanced），而實(shí)際上趨向于非常不平衡。
左式堆性質(zhì)我們把任意節(jié)點(diǎn) X 的零路徑長（null path length） npl(X) 定義為從 X 到一個(gè)不具有兩個(gè)兒子的節(jié)點(diǎn)的最短路徑長。因此，具有 0 個(gè)或一個(gè)兒子的節(jié)點(diǎn)的 npl 為 0，而 npl(null) = -1。
任意節(jié)點(diǎn)的零路徑長比它的所有兒子節(jié)點(diǎn)的零路徑長的最小值大1.這個(gè)結(jié)論也適用于少于兩個(gè)兒子的節(jié)點(diǎn)，因?yàn)?null 的零路徑長是 -1.
左式堆的性質(zhì)是：對于堆中的每一個(gè)節(jié)點(diǎn) X，左兒子的零路徑長大于等于右兒子的零路徑長。
實(shí)際上，對于左式堆的任意一個(gè)節(jié)點(diǎn)只能有三種情況，有兩個(gè)子節(jié)點(diǎn)、沒有子節(jié)點(diǎn)、僅有一個(gè)節(jié)點(diǎn)且該節(jié)點(diǎn)為左子節(jié)點(diǎn)。
也就是說，如果存在任意一個(gè)節(jié)點(diǎn)只有右節(jié)點(diǎn)，那么這個(gè)堆一定不是左式堆。但是，如果一個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)都滿足上面的條件，它不一定是左式堆，還需要滿足零路徑長的條件。
顯然，在上路中，左圖是一棵左式堆；而右圖則不是，因?yàn)橛覉D的根節(jié)點(diǎn)的左子節(jié)點(diǎn)的左子節(jié)點(diǎn)的零路徑長 == 0，而根節(jié)點(diǎn)的左子節(jié)點(diǎn)的右子節(jié)點(diǎn)的零路徑長 == 1.
這個(gè)性質(zhì)使得它不是一棵理想平衡樹，因?yàn)樗@然偏重于使樹向左增加深度。
因?yàn)樽笫蕉掩呄蛴诩由钭舐窂?，所以右路徑?yīng)該短。事實(shí)上，沿左式堆的右路徑是該堆中的最短路徑。否則，就會(huì)存在某個(gè)節(jié)點(diǎn) X 的左兒子的最短路徑長小于右兒子的最短路徑長。
node
/
node `node`
/ /
node node `null` node
例如，對于上面這個(gè)樹，對于標(biāo)記的 node 節(jié)點(diǎn)是不符合左式堆的，因?yàn)樗淖笞庸?jié)點(diǎn)的零路徑長是 -1，而右子節(jié)點(diǎn)的零路徑長是 0.
左式堆的基本操作左式堆的基本操作是合并。注意，插入只是合并的特殊性情況。
3 | 6 |
/ | / |
10 8 | 12 7 |
/ / | / / |
21 14 17 | 18 24 37 18 |
/ / | / |
23 26 | 33 |
合并具有大的 root 的堆與具有較小的 root 的堆的右節(jié)點(diǎn)
函數(shù)棧最上層
| 6 |
| / |
8 | 12 7 |
/ | / / |
17 | 18 24 37 18 |
/ | / |
26 | 33 |
函數(shù)棧的底層，該層等待上層函數(shù)的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
遞歸的去進(jìn)行 merge 操作
函數(shù)棧最上層
8 | 7 |
/ | / |
17 | 37 18 |
/ | |
26 | |
函數(shù)棧第二層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數(shù)棧的底層，該層等待上層函數(shù)的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
繼續(xù)進(jìn)行遞歸 merge
函數(shù)棧最上層
8 | |
/ | |
17 | 18 |
/ | |
26 | |
函數(shù)棧第二層
| 7 |
| / |
| 37 |
| |
| |
函數(shù)棧第三層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數(shù)棧的底層，該層等待上層函數(shù)的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
繼續(xù)進(jìn)行遞歸 merge
函數(shù)棧最上層，這個(gè)時(shí)候函數(shù)棧開始退出
null | 18 |
函數(shù)棧最二層
8 | |
/ | |
17 | |
/ | |
26 | |
函數(shù)棧第三層
| 7 |
| / |
| 37 |
| |
| |
函數(shù)棧第四層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數(shù)棧的底層，該層等待上層函數(shù)的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
函數(shù)棧開始退出
函數(shù)棧最上層，上層函數(shù)退出，同時(shí)必須更新 root 節(jié)點(diǎn)的 npl
8 | |
/ | |
17 18 | |
/ | |
26 | |
函數(shù)棧第二層
| 7 |
| / |
| 37 |
| |
| |
函數(shù)棧第三層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數(shù)棧的底層，該層等待上層函數(shù)的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
函數(shù)棧繼續(xù)退出，同時(shí)如果root左子樹的零路徑長小于右子樹的零路徑長則必須翻轉(zhuǎn)兩個(gè)子樹
函數(shù)棧最上層，上層函數(shù)退出，同時(shí)必須更新 root 節(jié)點(diǎn)的 npl
7
/
8 37 | |
/ | |
17 18 | |
/ | |
26 | |
函數(shù)棧第二層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數(shù)棧的底層，該層等待上層函數(shù)的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
最后得到的結(jié)果為 圖 6-24 所示。
遞歸的退出條件是：
被 merge 的兩個(gè)左式堆中任意一個(gè)為 null，則返回另一個(gè)；
兩個(gè)左式堆中那么具有較小 root 節(jié)點(diǎn)的左子節(jié)點(diǎn)為 null 時(shí)，將具有較大 root 的節(jié)點(diǎn)作為具有較小 root 的節(jié)點(diǎn)的左子節(jié)點(diǎn)，并返回具有較小 root 的幾點(diǎn)。這里隱含了一個(gè)信息：當(dāng)一個(gè)左式堆的左子節(jié)點(diǎn)為 null 時(shí)，它的右子節(jié)點(diǎn)必定為 null。因?yàn)槿绻易庸?jié)點(diǎn)不為 null，那么它就不滿足左式堆的條件了。
如果這兩個(gè)堆中有一個(gè)為空，那么我們可以返回另外一個(gè)堆。
否則合并他們：
首先，我們遞歸的將具有大的 root 的堆與具有小的 root的堆的右子堆合并。我們在遞歸算法中需要保證遞歸得到的這棵樹是左式堆。
為什么這里是合并較大 root 的堆和較小 root 的堆的右子堆呢？
因?yàn)?，我們合并出來的這個(gè)堆需要做為原來那個(gè)堆的右子堆，而根據(jù)左式堆的性質(zhì)，一個(gè)節(jié)點(diǎn)所有的子節(jié)點(diǎn)都必須大于該節(jié)點(diǎn)。
圖 6-23 得到的不是左式堆。左式的性質(zhì)在根處被破壞。
在我們步驟 1. 中得到的新的子樹是左式堆，而右子樹本身就是左式堆，所以這棵樹是不是滿足左式堆，只要左子樹的零路徑長大于新的右子樹的零路徑長即可。
如果不滿足，我們只需要將左子樹和右子樹的節(jié)點(diǎn)交換并更新零路徑長就可以了。
package com.mosby.ch06; /** * 左式堆：與普通二叉堆區(qū)別在于，左式堆不是一個(gè)完全二叉樹，并且左式堆不是一個(gè)理想平衡二叉樹。 */ public class LeftistHeap> { public LeftistHeap(){ root = null; } /** * 公有的 merge 方法將 anotherLeftistHeap 合并到控制堆中。 * 隨后 anotherLeftistHeap 變成了空的。 * 在第一趟，我們通過合并兩個(gè)堆的右路徑建立一棵新的樹。為此，以排序的方式安排 H1 和 H2 * 右路徑上的節(jié)點(diǎn)，保持他們各自的左兒子不變。 * 第二趟構(gòu)成堆，兒子的交換工作在左式堆性質(zhì)被破壞的那些節(jié)點(diǎn)上進(jìn)行。 *
* @param anotherLeftistHeap 被合并的左式樹 */ public void merge(LeftistHeapanotherLeftistHeap){ if(this == null){ return ; } root = merge(root, this.root); anotherLeftistHeap.root = null; } /** * 向左式樹中插入新的元素 *
* @param x */ public void insert(E x){ root = merge(new Node<>(x), root); } /** * 尋找左式堆中最小的元素 *
* @return 左式堆最小元素 */ public E findMin(){ if(isEmpty()){ return null; } return root.theElement; } /** * 刪除左式堆中最小元素，并返回該元素 *
* @return 被刪除的元素 */ public E deleteMin(){ if(isEmpty()){ return null; } E minItem = root.theElement; root = merge(root.left, root.right); return minItem; } /** * 返回左式堆是否為空 *
* @return */ public boolean isEmpty(){ return root == null; } /** * 將左式堆設(shè)置為空堆 */ public void makeEmpty(){ root = null; } /** * 內(nèi)部類用于表示左式堆的節(jié)點(diǎn)，相對于普通的二叉樹多了 npl（null path length）用于記錄空路徑長 *
* @param節(jié)點(diǎn)中的存儲(chǔ)的對象 */ private static class Node { Node(E theElement){ this(theElement, null, null); } Node(E theElement, Node left, Node right){ this.theElement = theElement; this.left = left; this.right = right; npl = 0; } E theElement; Node left; Node right; int npl; } private Node root; /** * merge 方法被用于消除一些特殊情形并保證 H1 有較小的根。 *
* @param h1 * @param h2 * @return */ private Nodemerge(Node h1, Node h2){ if(h1 == null){ return h2; } if(h2 == null){ return h1; } if(h1.theElement.compareTo(h2.theElement) < 0){ return merge1(h1, h2); }else{ return merge1(h2, h1); } } /** * merge1 執(zhí)行實(shí)際的合并操作，并且在 merge1 的調(diào)用中，h1 小于 h2 *
* @param h1 * @param h2 * @return */ private Nodemerge1(Node h1, Node h2){ //根據(jù)左式堆的性質(zhì)，如果 h1.left == null，那么 h1.right == null 也成立 if(h1.left == null){ h1.left = h2; }else{ h1.right = merge(h1.right, h2); if(h1.left.npl < h1.right.npl){ swapChildren(h1); } h1.npl = h1.right.npl + 1; } return h1; } private void swapChildren(Node t){ Node tmp = t.left; t.right = t.left; t.left = tmp; } }
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64801.html
摘要：二叉堆的有趣之處在于，其邏輯結(jié)構(gòu)上像二叉樹，卻是用非嵌套的列表來實(shí)現(xiàn)。二叉堆結(jié)構(gòu)性質(zhì)為了更好地實(shí)現(xiàn)堆，我們采用二叉樹。圖完全二叉樹有意思的是我們用單個(gè)列表就能實(shí)現(xiàn)完全樹。下列所示的代碼是完全二叉堆的實(shí)現(xiàn)。 優(yōu)先隊(duì)列的二叉堆實(shí)現(xiàn) 在前面的章節(jié)里我們學(xué)習(xí)了先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列（Queue）。隊(duì)列有一種變體叫做優(yōu)先隊(duì)列（Priority Queue）。優(yōu)先隊(duì)列的出隊(duì)（Dequ...
摘要：一個(gè)常見的例子就是優(yōu)先隊(duì)列，還有排序算法之一的堆排序。另外我們還將學(xué)習(xí)堆排序，并將使用實(shí)現(xiàn)堆。堆排序在堆排序中，我們需要用給定的值構(gòu)建一個(gè)一個(gè)堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構(gòu)建一個(gè)堆。 堆是什么？ 堆是基于樹抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個(gè)常見的例子就是優(yōu)先隊(duì)列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...
摘要：二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效快速的找出最大值和最小值，常應(yīng)用于優(yōu)先隊(duì)列和著名的堆排序算法中。 二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效、快速的找出最大值和最小值，常應(yīng)用于優(yōu)先隊(duì)列和著名的堆排序算法中。 二叉堆 二叉堆有以下兩個(gè)特性： 是一顆完全二叉樹，表示數(shù)的每一層都有左側(cè)和右側(cè)子節(jié)點(diǎn)（除最后一層的葉節(jié)點(diǎn)），并且最后一層的葉節(jié)點(diǎn)盡可能是左側(cè)子節(jié)點(diǎn) 二叉堆不是最小堆就是...
摘要：選擇問題概述從個(gè)數(shù)當(dāng)中選出第個(gè)最大者。基本的堆操作見數(shù)據(jù)結(jié)構(gòu)與算法分析用優(yōu)先隊(duì)列解決選擇問題算法將個(gè)元素讀入數(shù)組，對數(shù)組應(yīng)用算法。參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法分析語言描述尋找最小的個(gè)數(shù) 選擇問題（seletion problem）概述[1] 從N個(gè)數(shù)當(dāng)中選出第k個(gè)最大者。 最簡單的兩種算法： 算法A1：排序-->返回k位置的數(shù)。時(shí)間復(fù)雜度O(N^2) 算法A2：先讀入前k個(gè)數(shù)-->排序...
閱讀 2445·2021-09-22 15:41
閱讀 1462·2021-08-19 10:54
閱讀 1770·2019-08-23 15:11
閱讀 3410·2019-08-23 10:23
閱讀 1439·2019-08-22 16:28
閱讀 810·2019-08-22 15:11
閱讀 752·2019-08-22 14:53
閱讀 723·2019-08-22 13:49
