package com.thealgorithms.datastructures.heaps;
import java.util.ArrayList;
/*
* This is a leftist heap that follows the same operations as a
* binary min heap, but may be unbalanced at times and follows a
* leftist property, in which the left side is more heavy on the
* right based on the null-path length (npl) values.
*
* Source: https://iq.opengenus.org/leftist-heap/
*
*/
public class LeftistHeap {
private static final class Node {
private final int element;
private int npl;
private Node left;
private Node right;
// Node constructor setting the data element and left/right pointers to null
private Node(int element) {
this.element = element;
left = null;
right = null;
npl = 0;
}
}
private Node root;
// Constructor
public LeftistHeap() {
root = null;
}
// Checks if heap is empty
public boolean isEmpty() {
return root == null;
}
// Resets structure to initial state
public void clear() {
// We will put head is null
root = null;
}
// Merge function that merges the contents of another leftist heap with the
// current one
public void merge(LeftistHeap h1) {
// If the present function is rhs then we ignore the merge
root = merge(root, h1.root);
h1.root = null;
}
// Function merge with two Nodes a and b
public Node merge(Node a, Node b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
// Violates leftist property, so must do a swap
if (a.element > b.element) {
Node temp = a;
a = b;
b = temp;
}
// Now we call the function merge to merge a and b
a.right = merge(a.right, b);
// Violates leftist property so must swap here
if (a.left == null) {
a.left = a.right;
a.right = null;
} else {
if (a.left.npl < a.right.npl) {
Node temp = a.left;
a.left = a.right;
a.right = temp;
}
a.npl = a.right.npl + 1;
}
return a;
}
// Function insert. Uses the merge function to add the data
public void insert(int a) {
root = merge(new Node(a), root);
}
// Returns and removes the minimum element in the heap
public int extractMin() {
// If is empty return -1
if (isEmpty()) {
return -1;
}
int min = root.element;
root = merge(root.left, root.right);
return min;
}
// Function returning a list of an in order traversal of the data structure
public ArrayList<Integer> inOrder() {
ArrayList<Integer> lst = new ArrayList<>();
inOrderAux(root, lst);
return new ArrayList<>(lst);
}
// Auxiliary function for in_order
private void inOrderAux(Node n, ArrayList<Integer> lst) {
if (n == null) {
return;
}
inOrderAux(n.left, lst);
lst.add(n.element);
inOrderAux(n.right, lst);
}
}