Leftist Heap is a #202202071755 that seek to improve Merge operations. It is usually left-heavy.
Characteristics
- The null path length of the left child of a node must not smaller than that of its right child.
- Insert and DeleteMin is done with Merge.
Analysis
- Merge will result in \(O(\log N)\)
- Insert and DeleteMin will result in \(O(\log N)\) too like Merge
Implementation
#ifndef _LeftHeap_H
struct TreeNode;
typedef struct TreeNode *PriorityQueue;
PriorityQueue Initialise(void);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2);
#define Insert(X, H) (H = Insert1((X), H))
#define DeleteMin(H) (H = DeleteMin1(H))->Element
PriorityQueue Insert1(ElementType X, PriorityQueue H);
PriorityQueue DeleteMin1(PriorityQueue H);
#endif
struct TreeNode {
ElementType Element;
PriorityQueue Left;
PriorityQueue Right;
int Npl;
};
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);
}
static PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2) {
if (H1->Left == NULL) // Single Node
H1->Left = H2; // H1->Right is already NULL, H1->Npl is already 0
else {
H1->Right = Merge(H1->Right, H2);
if (H1->Left->Npl < H1->Right->Npl)
SwapChildren(H1);
H1->Npl = H1->Right->Npl + 1;
}
}
PriorityQueue Insert1(ElementType X, PriorityQueue H) {
PriorityQueue SingleNode;
SingleNode = malloc(sizeof(struct TreeNode));
if (SingleNode == NULL)
FatalError("Out of space!!!");
else {
SingleNode->Element = X;
SingleNode->Npl = 0;
SingleNode->Left = SingleNode->Right = NULL;
H = Merge(SingleNode, H);
}
}
PriorityQueue DeleteMin1(PriorityQueue H) {
PriorityQueue LeftHeap, RightHeap;
if (IsEmpty(H)) {
Error("Priority queue is empty");
return H;
}
LeftHeap = H->Left;
RightHeap = H->Right;
free(H);
return Merge(LeftHeap, RightHeap);
}