1、NPL（零路徑長）：從x到一個沒有兒子的節點的最短路徑的長。

具有一個或者0個兒子的節點的NPL為0，NPL（NULL）=-1。

任意節點的零路徑長比它的兒子的零路徑長的最小值多1。

2、左式堆

（1）滿足二叉堆的所有性質。

（2）對于堆的每一個節點x，左兒子的零路徑長度至少與右兒子的零路徑長度一樣大（即NPL（Left）>=NPL（Right））

3、性質：

在右路徑上有r個節點的左式樹至少有2^r-1個節點。

（N個節點的左式樹的一條右路徑最多含有log（N+1）個節點）

4、具體操作：

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; struct Node{int data,Npl;struct Node *Left,*Right; }; typedef struct Node* PriorityQueue; PriorityQueue Merge1(PriorityQueue Q1,PriorityQueue Q2);bool IsEmpty(PriorityQueue Q) //與二叉堆的判斷是否為空的方式相同 {return Q==NULL; }PriorityQueue Merge(PriorityQueue Q1,PriorityQueue Q2) //合并兩個左式堆 {if(Q1==NULL) return Q2;if(Q2==NULL) return Q1;if(Q1->data<Q2->data) return Merge1(Q1,Q2);else return Merge1(Q2,Q1); }PriorityQueue Merge1(PriorityQueue Q1,PriorityQueue Q2) {if(Q1->Left==NULL) Q1->Left=Q2;else{Q1->Right=Merge(Q1->Right,Q2);if(Q1->Left->Npl<Q1->Right->Npl){PriorityQueue tp=Q1->Left;Q1->Left=Q1->Right;Q1->Right=tp;}Q1->Npl=Q1->Right->Npl+1;}return Q1; }PriorityQueue Insert1(int x,PriorityQueue Q) //插入 {PriorityQueue tp=new Node;if(tp==NULL) printf("Out of Space!!!\n");else{tp->data=x;tp->Left=tp->Right=0;tp->Npl=1;Q=Merge(tp,Q);}return Q; }PriorityQueue DeleteMin1(PriorityQueue Q) //刪除最小值，就是出隊 {PriorityQueue Left,Right;if(IsEmpty(Q)){printf("The Priority Queue is Empty!!!\n");}else{Left=Q->Left;Right=Q->Right;free(Q);return Merge(Left,Right);}return Q; } void Print(PriorityQueue Q) //輸出最終結果 {if(Q){Print(Q->Left);printf("%d ",Q->data);Print(Q->Right);} } int main(void) {PriorityQueue Q1=NULL,tp,Q2=NULL;int n,m,i,x;cin>>n;for(i=0;i<n;i++){scanf("%d",&x);Q1=Insert1(x,Q1);}Print(Q1);cout<<endl;cin>>m;for(i=0;i<m;i++){scanf("%d",&x);Q2=Insert1(x,Q2);}Print(Q2);cout<<endl;tp=Merge(Q1,Q2);Print(tp);cout<<endl;while(!IsEmpty(tp)){printf("%d ",tp->data);tp=DeleteMin1(tp);}return 0; } /* 測試數據： 4 1 2 3 4 6 7 8 9 5 10 11 */ View Code

?

轉載于:https://www.cnblogs.com/2018zxy/p/10338041.html

總結

以上是生活随笔為你收集整理的优先队列：左式堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。