Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Time Complexities
1.2.
Properties
1.3.
Operations
1.4.
S-value or Dist
1.5.
Merging
1.5.1.
Merging visualization
1.6.
Inserting into a leftist heap
1.7.
Deleting Min element from a leftist heap
1.8.
Implementation
1.8.1.
Output
2.
Frequently Asked Questions
2.1.
What is a heap data structure?
2.2.
What is a Leftist Heap?
3.
Conclusion
Last Updated: Mar 27, 2024
Easy

Leftist Heap

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Heap and Priority Queue

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 s-value. 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 one-node 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:
  1. Key(i) >= Key(parent(i)): This is similar to normal min-heap property.
  2. The right descendant of every node has a smaller s-value. 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:
  1. The smallest path from any leaf to the root is the path from the root to the rightmost leaf.
  2. If there are ‘X’ nodes in the path from the root to the rightmost leaf, then the leftist heap will have at least (2x - 1) nodes. 
  3. 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

  1. merge(): The main operation of a leftist heap is the merge operation.
  2. deleteMin(): This can be done by replacing the minimum node with the merge of left and right subtrees.
  3. insert(): This can be done by calling the merge function on the original heap and a new one-node heap.

S-value or Dist

The s-value (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:

  1. Make the root with a smaller value than the new root.
  2. Push this root into an empty stack and move to its right child.
  3. Recursively compare the two keys, keep pushing the smaller key into the stack, and move to its right child.
  4. Perform step 3 until a null node is reached.
  5. Pick the last node processed and make it the right child of the node present at the top of the stack. 
  6. 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

Merge 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.

  1. newHeap = createLeftistHeap(val)
  2. merge(leftistHeap, newHeap)

Deleting Min element from a leftist heap

The min-element is the root of a leftist heap. So, to delete the min-element, we replace the root element with the merge of its left and right subtrees.

  1. Val = root.val
  2. root = merge(root.right, root.left)
  3. 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 tree-based data structure that satisfies the following properties:
It is almost a complete tree.
In a min-heap, 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 s-value. In contrast to a binary heap, which is always a complete binary tree, a leftist heap attempts to be very unbalanced. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Conclusion

In this article, we learned what is a leftist heap. We saw various properties of a leftist heap, the operations that can be performed on it, and their time complexities. We also saw the C++ implementation of a leftist heap. If you want to learn more about such topics, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends! To be more confident in Data Structures and algorithms, try out our DS and Algo Course.

Check out this problem - Root To Leaf Path

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Fibonacci Heap
Next article
N-ary Heap
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass