数据结构-左式堆

左式堆：同二叉堆一样具有结构性和堆序性。惟一的区别是：左式堆不是理想平衡的，而实际上是趋于不平衡的。

零路径长（NPL（x））：从节点x到一个没有两个儿子节点的最短路径长。

左式堆要求对于堆中的每一个节点x，左儿子的零路径长至少与右儿子的零路径长一样大。

左式堆的结构声明：

struct treeNode; typedef struct treeNode *priorityQueue; struct treeNode { int element; priorityQueue left; priorityQueue right; int npl; }; priorityQueue initialize(priorityQueue h); void swapChildren(priorityQueue h); priorityQueue merge(priorityQueue h1, priorityQueue h2); static priorityQueue merge1(priorityQueue h1, priorityQueue h2); priorityQueue insert1(int x, priorityQueue h); int isEmpty(priorityQueue h); priorityQueue deleteMin1(priorityQueue h); void printQueue(priorityQueue h); 合并左式堆的驱动例程： priorityQueue merge(priorityQueue h1, priorityQueue h2) { if (h1 == NULL) return h2; if (h2 == NULL) return h1; if (h1->element < h2->element) return merge1(h1, h2); else return merge1(h2, h1); } 合并左式堆的实际例程：

void swapChildren(priorityQueue h) { priorityQueue r = h->left; h->left = h->right; h->right = r; } static priorityQueue merge1(priorityQueue h1, priorityQueue h2) { 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; } 插入例程：

priorityQueue insert1(int x, priorityQueue h) { priorityQueue singleNode; singleNode = (struct treeNode *)malloc(sizeof(struct treeNode)); if (singleNode == NULL) cout << "Out of space!" << endl; else { singleNode->element = x; singleNode->npl = 0; singleNode->right = singleNode->left = NULL; h = merge(singleNode, h); } return h; } DeleteMin例程：

int isEmpty(priorityQueue h) { if (h == NULL) return 1; else return 0; } priorityQueue deleteMin1(priorityQueue h) { priorityQueue leftHeap, rightHeap; if (isEmpty(h)) { cout << "Queue is null!" << endl; return h; } leftHeap = h->left; rightHeap = h->right; free(h); return merge(leftHeap, rightHeap); }