Leftist Heap

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);
}
Links to this page
#data-structure #heap