【0】README

0.1） 本文文字描述部分轉(zhuǎn)自 數(shù)據(jù)結(jié)構(gòu)與算法分析， 旨在理解 優(yōu)先隊(duì)列——左式堆 的基礎(chǔ)知識(shí)；
0.2） 本文核心思路均為原創(chuàng)， 源代碼部分借鑒 數(shù)據(jù)結(jié)構(gòu)與算法分析 ；
0.3） for original source code, please visit https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter6/p145_leftist_heap

1）相關(guān)定義

• 1.1）零路徑長(zhǎng)度定義： 到?jīng)]有兩個(gè)兒子的節(jié)點(diǎn)最短距離， 即零路徑長(zhǎng)Npl 定義為 從 X 到一個(gè)沒(méi)有兩個(gè)兒子的 節(jié)點(diǎn)的最短路徑的長(zhǎng)；也即， 非葉子節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最少邊數(shù)，其中NULL的零路徑長(zhǎng)為-1， 葉子節(jié)點(diǎn)的零路徑長(zhǎng)為0；（干貨——零路徑長(zhǎng)的定義—— 非葉子節(jié)點(diǎn)到葉子節(jié)點(diǎn)或只有一個(gè)兒子的節(jié)點(diǎn)的最少邊數(shù)，非常重要，因?yàn)樽笫蕉训亩x是基于零路徑長(zhǎng)的定義的）
  

• 1.２）左式堆定義：一棵具有堆序性質(zhì)的二叉樹(shù)　＋　零路徑長(zhǎng)：左兒子 ≧ 右兒子　＋　父節(jié)點(diǎn) = min{兒子} +1；（干貨——左式堆的定義是建立在具有堆序性的二叉樹(shù)上，而不是二叉堆上）

2）merge操作原則： 根值大的堆與根值小的堆的右子堆合并；（干貨——merge操作原則）
3）merge操作存在的三種情況（設(shè)堆H1的根值小于H2）

• case1） H1只有一個(gè)節(jié)點(diǎn)；
• case2） H1根無(wú)右孩子；
• case3） H1根有右孩子；

---

補(bǔ)充（Complementary）：左式堆合并操作詳解（merge）

左式堆合并原則：大根堆H2與小根堆H1的右子堆合并 （干貨——左式堆合并原則）
具體分三種情況（設(shè)堆H1的根值小于H2）

• case1）H1只有一個(gè)節(jié)點(diǎn)（只有它自己而已）： H1只有一個(gè)節(jié)點(diǎn)，若出現(xiàn)不滿(mǎn)足 零路徑長(zhǎng)：左兒子≧右兒子，交換左右孩子；
  
  
  • Attention）上例中（中間所示堆），左兒子的零路徑長(zhǎng)為-1， 而右兒子的零路徑長(zhǎng)為0，所以不滿(mǎn)足左式堆的條件， 需要交換左右孩子；
• case2）H1根無(wú)右孩子： H1根無(wú)右孩子，若出現(xiàn)不滿(mǎn)足：零路徑長(zhǎng)：左兒子≧右兒子，需要交換左右孩子。
  
  
  • Attention）上例中（中間所示堆），左兒子的零路徑長(zhǎng)為0， 而右兒子的零路徑長(zhǎng)為1，所以不滿(mǎn)足左式堆的條件，需要交換；
• case3）H1根有右孩子：
  
  • step1）截取H1的右子堆R1， 和截取H2的右子堆R2；
  • step2）將R1 與 R2進(jìn)行merge操作得到H3， 且取R1和R2中較小根作為新根； （Attention： 現(xiàn)在你將看到，截取后的H1 和 H2， 以及新生成的H3 都是 case2）；
  • step3）比較H3的左右孩子，是否滿(mǎn)足左式堆要求，如果不滿(mǎn)足則交換左右孩子；
  • step4）將H3與沒(méi)有右子堆的H1進(jìn)行merge操作，也即最后將case3 轉(zhuǎn)換為了 case2；
    
    

Conclusion） 現(xiàn)在才知道，左式堆的merge操作其實(shí)是一個(gè)遞歸的過(guò)程， 看如下解析； （干貨——這是最后解析merge操作啦）

Attention once again）

• A1）左式堆是建立在具有堆序性的二叉樹(shù)上；
• A2）左式堆是建立在零路徑長(zhǎng)上；
• A3）左式堆的核心操作是 merge， 無(wú)論insert 還是 deleteMin 都是基于 merge操作的；
• A4）左式堆的merge操作執(zhí)行后，還要update 左式堆根節(jié)點(diǎn)的零路徑長(zhǎng)， 左式堆根節(jié)點(diǎn)的零路徑長(zhǎng) == min{兒子的零路徑長(zhǎng)} +1；
• A5） update 后， 還需要比較 左右零路徑長(zhǎng) 是否滿(mǎn)足左式堆的定義， 如果不滿(mǎn)足，還需要交換左式堆根節(jié)點(diǎn)的左右孩子；

---

source code at a glance）

#include "leftist_heap.h" // swap the left and the right in priority queue. void swap(PriorityQueue h1) {PriorityQueue temp;temp = h1->left;h1->left = h1->right;h1->right = temp; }// analog print directories and files name in the BinaryTree, which involves postorder traversal. void printPreorder(int depth, TreeNode root) { int i;if(root) { for(i = 0; i < depth; i++)printf(" "); printf("%d\n", root->value);printPreorder(depth + 1, root->left); // Attention: there's difference between traversing binary tree and common tree.printPreorder(depth + 1, root->right);}else {for(i = 0; i < depth; i++)printf(" "); printf("NULL\n");} }// insert an element with value into the priority queue. PriorityQueue insert(ElementType value, PriorityQueue pq) {TreeNode node; node = (TreeNode)malloc(sizeof(struct TreeNode));if(!node){Error("failed inserting, for out of space !");return pq;}node->left = NULL;node->right = NULL;node->nullPathLen = 0;node->value = value; if(pq == NULL) // means that just only creating a node with value.{return node;}else{return merge(node, pq); } }// return the minimal between a and b. int minimal(int a, int b) {return a > b ? b : a; }// merge the priority queue h1 and h2. PriorityQueue merge(PriorityQueue h1, PriorityQueue h2) { if(h1 == NULL){return h2;}else if(h2 == NULL){return h1;} if(h1->value > h2->value){return innerMerge(h2, h1);}else{return innerMerge(h1, h2);} }// merge the priority queue h1 and h2. PriorityQueue innerMerge(PriorityQueue h1, PriorityQueue h2) { if(h1->left == NULL){h1->left = h2;}else{h1->right = merge(h1->right, h2);} // update the null path lengthif(h1->right == NULL){h1->nullPathLen = 0;}else{h1->nullPathLen = minimal(h1->left->nullPathLen, h1->right->nullPathLen) + 1; // exchange the left and the rightif(h1->left->nullPathLen < h1->right->nullPathLen){swap(h1);}}return h1; }// delete the minimal element in the priority queue. PriorityQueue deleteMin(PriorityQueue h1) {PriorityQueue left;PriorityQueue right;if(!h1){Error("failed deleteMin, for the root doesn't point to any position!");return NULL;}left = h1->left;right = h1->right;free(h1);return merge(left, right); }int main() {PriorityQueue h1;PriorityQueue h2; int data[] = {21, 10, 23, 14, 3, 26, 17, 8}; int data2[] = {18, 12, 33, 24, 6, 37, 7, 18}; int i;h1 = insert(data[0], NULL);for(i=1; i<8; i++){h1 = insert(data[i], h1);}printf("\n=== after the leftist heap h1 is merged===\n");printPreorder(1, h1);h2 = insert(data2[0], NULL);for(i=1; i<8; i++){h2 = insert(data2[i], h2);}printf("\n=== after the leftist heap h2 is merged===\n");printPreorder(1, h2);h1 = merge(h1, h2);printf("\n=== after both h1 and h2 are merged===\n");printPreorder(1, h1);h1 = deleteMin(h1);printf("\n=== after executing deleteMin operation ===\n");printPreorder(1, h1);return 0; }

---

printing results are as follows）

總結(jié)

以上是生活随笔為你收集整理的优先队列——左式堆的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。