1樓：匿名使用者
左式堆學習
部落格分類： 資料結構
演算法資料結構
今天學習了一下左式堆，總結一下。
一、左式堆定義：
具有，如下性質
1、父節點屬性值小於子節點屬性值；
2、堆中的任何節點，其左兒子的零路徑長》=右兒子的零路徑長；
的二叉樹。
注：零路徑長(npl)是指：從乙個節點x開始到乙個不具有兩個兒子的y節點的最短路徑的長，可以看出有0個或者乙個兒子的節點的npl=0，並且定義npl(null)=-1；
二、左式對的節點定義：
java**
class node
public node(t element, nodeleft, noderight)
} class node
public node(t element, nodeleft, noderight)
} 三、左式對的操作：
對於左式堆主要操作是「合併」，因為合併會破壞左式堆的特性，而insert、delete等操作，都會涉及到堆的合併，例如：delete根節點，相當於將一棵樹邊為了兩個樹，在將兩棵樹合併為一棵樹。這裡我們使用了一種遞迴的思想，若h1，h2本身是左式堆，則其子樹也一定是左式堆，其子樹的子樹也一定是左式堆，一直退到樹的每個葉子節點，都符合這個規則，那麼我們合併時就可以從反方向思考，先形成乙個個的小左式堆，然後在形成一棵大的左式堆。
四、左式堆定義**：
java**
public class leftistheap>
public node(t element, nodeleft, noderight)
}private noderoot;
public leftistheap()
// 合併兩個左式堆
public void merge(leftistheaprhs)
// 向左式堆中新增元素
public void insert(t element)
// 找尋左式堆中最小節點
public t findmin()
/*** 刪除堆中最小節點，由於堆的最小節點就在根上，所以可以直接刪除，但是刪除根後，需要在將左右子樹合併
** @return
*/public t deletemin()
// 判斷左式堆是否為空
public boolean isempty()
// 將左式堆設定為空堆
public void makeempty()
/*** 1、若第乙個根節點為空，則返回第二個根節點； 2、若第乙個不為空第二個為空，則返回第乙個根節點；
* 3、
一、二節點都不為空時，判斷那個是根較小的節點，將根較小的節點作為第乙個引數傳遞給merge1方法
** @param h1
* @param h2
* @return
*/private nodemerge(nodeh1, nodeh2) else
}/*** 將根節點較大的樹合併到根節點較小的樹上去： 1、若根節點較小的樹無左子樹，則將根節點較大的樹作為其左子樹
* 2、若根節點較小的樹有左子樹，則將根節點較大的樹和根節點較小的樹的右子樹合併，作為根節點較小的樹的右子樹
* 3、若左子樹的零路徑長小於右子樹的零路徑長，則交換左右子樹 4、根節點較小的樹的零路徑長修正為其右子樹的零路徑長度+1
** @param h1
* @param h2
* @return
*/private nodemerge1(nodeh1, nodeh2)
return h1;
}// 交換兩個子樹
private void swapchildren(nodet)
} public class leftistheap>
public node(t element, nodeleft, noderight)
}private noderoot;
public leftistheap()
// 合併兩個左式堆
public void merge(leftistheaprhs)
// 向左式堆中新增元素
public void insert(t element)
// 找尋左式堆中最小節點
public t findmin()
/*** 刪除堆中最小節點，由於堆的最小節點就在根上，所以可以直接刪除，但是刪除根後，需要在將左右子樹合併
* * @return
*/public t deletemin()
// 判斷左式堆是否為空
public boolean isempty()
// 將左式堆設定為空堆
public void makeempty()
/*** 1、若第乙個根節點為空，則返回第二個根節點； 2、若第乙個不為空第二個為空，則返回第乙個根節點；
* 3、
一、二節點都不為空時，判斷那個是根較小的節點，將根較小的節點作為第乙個引數傳遞給merge1方法
* * @param h1
* @param h2
* @return
*/private nodemerge(nodeh1, nodeh2) else
}/**
* 將根節點較大的樹合併到根節點較小的樹上去： 1、若根節點較小的樹無左子樹，則將根節點較大的樹作為其左子樹
* 2、若根節點較小的樹有左子樹，則將根節點較大的樹和根節點較小的樹的右子樹合併，作為根節點較小的樹的右子樹
* 3、若左子樹的零路徑長小於右子樹的零路徑長，則交換左右子樹 4、根節點較小的樹的零路徑長修正為其右子樹的零路徑長度+1
* * @param h1
* @param h2
* @return
*/private nodemerge1(nodeh1, nodeh2)
return h1;
}// 交換兩個子樹
private void swapchildren(nodet)
} 參考資料：《資料結構與演算法分析--java語言描述》mark allen weiss著
斜堆(skew heap)也叫自適應堆(self-adjusting heap)，是一種使用二叉樹實現的堆狀資料結構。 斜堆的優勢是其合併的速度遠遠大於二叉堆。 斜堆是一種自適應的左偏樹。
編輯本段定義
斜堆可遞迴的定義如下： ● 只有乙個元素的堆是斜堆。 ● 兩個斜堆通過斜堆的合併操作，得到的結果仍是斜堆。
編輯本段操作
合併我們可以用左偏樹的合併演算法實現兩個斜堆的合併。 除此之外，還有一種非遞迴的演算法。 ● 分割每個堆。
方法是從根節點開始，右子樹與根節點分離，然後右子樹以同樣的方式分割。 最後得到乙個樹的集合，集合中的樹的特點是：其根節點只有左子樹或者沒有子樹。
● 對集合中的樹，按照根節點的值從小到大排序。 ● 從右到左，不斷地合併最後兩個子樹，直到只剩下一棵樹。 合併方法是：
● 如果倒數第二棵樹有左子樹，那麼把左子樹變為右子樹。 ● 把最後一棵樹作為倒數第二棵樹的左子樹。
資料結構中*和&有什麼區別？
2樓：9小王子非魚
資料結構中*是取位址內容，和c語言用法一樣。而&的用法有兩種，一種是取位址運算子，和c語言的一樣，另一種是引用，參考了c++的用法。
*有兩個意思，一是定義指標時使用：int* p=pa；另乙個是解引用時使用：cout<<*p<&也有兩個意思，一是取位址時使用：
int* p=&a;另乙個是定義引用時使用：int& a=b。
*&的意思是指標的引用，一般在函式的傳參時使用，表示將指標直接傳給函式，不是僅僅複製指標的位址作為副本進行傳遞。
資料結構中弧和路徑的區別,資料結構中和有什麼區別
這兩個概念差太遠了bai吧du?弧 指的是有向圖裡面的邊,zhi 他是有明確方向的。如dao果是專無向圖的邊,直接叫做 邊 屬。比如有向圖的 v1 結點到 v2 結點的弧可能是 路徑 指的是圖 包括有向圖和無向圖 裡面連線兩個結點之間的邊的集合,也就是乙個頂點序列。比如 v1 到 v3 的路徑可能這...
資料結構中typedefstruct用法
在c語言中，可以使用結構體 struct 來存放一組不同型別的資料。結構體的定義形式為 struct 結構體名 結構體所包含的變數或陣列 結構體是一種集合，它裡面包含了多個變數或陣列，它們的型別可以相同，也可以不同，每個這樣的變數或陣列都稱為結構體的成員 member 結構體定義 第一種 只有結構體...
在資料結構中,資料的邏輯結構,資料的儲存結構及資料的運算之間
資料的邏輯結構決定了資料間運算關係的具體定義，而資料的儲存結構與資料的運算方法，沒有直接的關係，資料的儲存結構決定了維護資料邏輯結構時各種操作的運算複雜程度。在資料結構課程中，資料的邏輯結構，資料的儲存結構及資料的運算之間存在著怎樣的關係？1 資料的邏輯結copy構說明資料元素bai之間的順序du關...