Introduction
A leftist heap or leftist tree is a priority queue. It is implemented with a variant of the binary heap. We store the distance of the nearest leaf in the subtree rooted at a node for every node. Let us call this value svalue. Leftist heap attempts to be very unbalanced which is in contrast to a binary heap, which is always a complete binary tree.
Also see, Implementation of Heap
A leftist heap is an implementation of a mergeable heap. While inserting a new node into the heap, a new onenode heap is created, which is merged into the existing heap. To delete an item, we replace it with the merge of its left and right subtrees.
Leftist heaps are useful because of their ability to merge quickly (in O(logN) time) compared to binary heaps that take O(N) time.
Also Read, Prefix Sum Array
Time Complexities
The following are the time complexities of various operations of a leftist heap:
Function  Complexity 
Get Min  O(1) 
Delete Min  O(logN) 
Insert  O(logN) 
Merge  O(logN) 
Properties
 The following are the properties of a leftist heap:
 Key(i) >= Key(parent(i)): This is similar to normal minheap property.

The right descendant of every node has a smaller svalue. This means that the number of edges on the shortest path from a node to a leaf of the right child is less than or equal to that of the left child.
 From the above properties, we can conclude the following:
 The smallest path from any leaf to the root is the path from the root to the rightmost leaf.
 If there are ‘X’ nodes in the path from the root to the rightmost leaf, then the leftist heap will have at least (2^{x}  1) nodes.
 From point 2, we can also conclude that the length of the path from the root to the leftmost leaf is O(logN) for a leftist heap having N nodes.
Operations
 merge(): The main operation of a leftist heap is the merge operation.
 deleteMin(): This can be done by replacing the minimum node with the merge of left and right subtrees.
 insert(): This can be done by calling the merge function on the original heap and a new onenode heap.
Svalue or Dist
The svalue (or dist) of a node is the distance between that node and the nearest leaf in the subtree of that node. The dist of a null child is 0 (In some implementations, the dist of a null child is assumed to be 1).
Merging
Since the right subtree of a leftist heap is smaller than the left subtree, we merge the right subtree with the other tree.
The following are the steps for merge operation:
 Make the root with a smaller value than the new root.
 Push this root into an empty stack and move to its right child.
 Recursively compare the two keys, keep pushing the smaller key into the stack, and move to its right child.
 Perform step 3 until a null node is reached.
 Pick the last node processed and make it the right child of the node present at the top of the stack.
 Recursively pop the elements from the stack and keep making them the right child of the new node present at the stack top.
Merging visualization
Inserting into a leftist heap
The insertion operation is done using the merge operation. We create a new leftist heap with a single node having a value of the element to be inserted. We then merge this newly created heap with the existing heap.
 newHeap = createLeftistHeap(val)
 merge(leftistHeap, newHeap)
Deleting Min element from a leftist heap
The minelement is the root of a leftist heap. So, to delete the minelement, we replace the root element with the merge of its left and right subtrees.
 Val = root.val
 root = merge(root.right, root.left)
 Return val
Implementation
// C++ program for leftist heap / leftist tree
#include <bits/stdc++.h>
using namespace std;
// Defining class Node for leftist heap node.
class Node
{
public:
int val;
Node *left;
Node *right;
int dist;
Node(int &val, Node *lt = NULL, Node *rt = NULL, int np = 0)
{
this>val = val;
right = rt;
left = lt,
dist = np;
}
};
// Defining Leftist Heap functions.
class LeftistHeap
{
public:
LeftistHeap();
LeftistHeap(LeftistHeap &rhs);
~LeftistHeap();
bool isEmpty();
bool isFull();
int &findMin();
void Insert(int &x);
void deleteMin();
void deleteMin(int &minItem);
void makeEmpty();
void Merge(LeftistHeap &rhs);
LeftistHeap &operator=(LeftistHeap &rhs);
private:
Node *root;
Node *Merge(Node *h1,
Node *h2);
Node *Merge1(Node *h1,
Node *h2);
void swapChildren(Node *t);
void reclaimMemory(Node *t);
Node *clone(Node *t);
};
// Function to construct leftist heap
LeftistHeap::LeftistHeap()
{
root = NULL;
}
// Copy constructor.
LeftistHeap::LeftistHeap(LeftistHeap &rhs)
{
root = NULL;
*this = rhs;
}
// Destructor for the leftist heap
LeftistHeap::~LeftistHeap()
{
makeEmpty();
}
// Function to merge rhs into the priority queue.
void LeftistHeap::Merge(LeftistHeap &rhs)
{
if (this == &rhs)
return;
root = Merge(root, rhs.root);
rhs.root = NULL;
}
// Function to merge two roots
Node *LeftistHeap::Merge(Node *h1,
Node *h2)
{
if (h1 == NULL)
return h2;
if (h2 == NULL)
return h1;
if (h1>val < h2>val)
return Merge1(h1, h2);
else
return Merge1(h2, h1);
}
// Function to merge two roots.
Node *LeftistHeap::Merge1(Node *h1,
Node *h2)
{
if (h1>left == NULL)
h1>left = h2;
else
{
h1>right = Merge(h1>right, h2);
if (h1>left>dist < h1>right>dist)
swapChildren(h1);
h1>dist = h1>right>dist + 1;
}
return h1;
}
// Function to swap children of a node.
void LeftistHeap::swapChildren(Node *t)
{
Node *tmp = t>left;
t>left = t>right;
t>right = tmp;
}
// Function to insert an item into leftist heap
void LeftistHeap::Insert(int &x)
{
root = Merge(new Node(x), root);
}
// Function to find the smallest item.
int &LeftistHeap::findMin()
{
return root>val;
}
// Function to remove the smallest item.
void LeftistHeap::deleteMin()
{
Node *oldRoot = root;
root = Merge(root>left, root>right);
delete oldRoot;
}
// Function to remove the smallest item.
void LeftistHeap::deleteMin(int &minItem)
{
if (isEmpty())
{
cout << "Heap is Empty" << endl;
return;
}
minItem = findMin();
deleteMin();
}
// Function to test if the priority queue is logically empty.
bool LeftistHeap::isEmpty()
{
return root == NULL;
}
// Function to test if the priority queue is logically full.
bool LeftistHeap::isFull()
{
return false;
}
// Make the priority queue logically empty
void LeftistHeap::makeEmpty()
{
reclaimMemory(root);
root = NULL;
}
// Deep copy
LeftistHeap &LeftistHeap::operator=(LeftistHeap &rhs)
{
if (this != &rhs)
{
makeEmpty();
root = clone(rhs.root);
}
return *this;
}
// Internal method to make the tree empty.
void LeftistHeap::reclaimMemory(Node *t)
{
if (t != NULL){
reclaimMemory(t>left);
reclaimMemory(t>right);
delete t;
}
}
// Internal method to clone subtree.
Node *LeftistHeap::clone(Node *t)
{
if (t == NULL){
return NULL;
}
else{
return new Node(t>val, clone(t>left), clone(t>right), t>dist);
}
}
// Driver program
int main()
{
LeftistHeap h;
LeftistHeap h1;
LeftistHeap h2;
int x;
int arr[] = {1, 5, 7, 10, 15};
int arr1[] = {22, 75};
h.Insert(arr[0]);
h.Insert(arr[1]);
h.Insert(arr[2]);
h.Insert(arr[3]);
h.Insert(arr[4]);
h1.Insert(arr1[0]);
h1.Insert(arr1[1]);
h.deleteMin(x);
cout << x << endl;
h1.deleteMin(x);
cout << x << endl;
h.Merge(h1);
h2 = h;
h2.deleteMin(x);
cout << x << endl;
return 0;
}
Output
1
22
5
Frequently Asked Questions
What is a heap data structure?
A heap is a treebased data structure that satisfies the following properties:
It is almost a complete tree.
In a minheap, the value of the parent of a node is less than or equal to the child of that node. Thus, the node at top of the heap has a minimum value.
What is a Leftist Heap?
A leftist heap or leftist tree is a priority queue. It is implemented with a variant of the binary heap. We store the distance of the nearest leaf in the subtree rooted at a node for every node. Let us call this value svalue. In contrast to a binary heap, which is always a complete binary tree, a leftist heap attempts to be very unbalanced.