Implement Skew Heap
Skew Heap is a type of binary heap that is used to implement priority queues. It is also sometimes called a self-adjusting heap or a biased merge heap.
Skew Heap has the same shape properties as a binary heap, but unlike a binary heap, it does not maintain a strict order between parent and child nodes. Instead, it allows the heap to become unbalanced by arbitrarily swapping subtrees during merge operations.
The merge operation of Skew Heap is defined as a recursive process that merges two heaps into a single heap. This process involves swapping the left and right sub-heaps of a node before merging them. This swapping process helps to keep the heap balanced by avoiding the creation of long chains of nodes with the same priority.
One of the advantages of Skew Heap is that it has a fast merge operation. It has an amortized time complexity of O(log n) per merge, where n is the total number of elements in the heap. This makes it useful in situations where frequent merging of priority queues is required.
However, Skew Heap has a worst-case time complexity of O(n) for certain operations such as delete-min, where n is the number of elements in the heap. This can make it inefficient for certain types of operations, especially when the heap is heavily skewed.
Here given code implementation process.
/*
C Program
Skew heap
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode*left;
struct TreeNode*right;
};
// SkewHeap Tree
struct SkewHeap
{
struct TreeNode*root;
};
// Create new tree
struct SkewHeap* new_tree()
{
// Create dynamic node
struct SkewHeap *tree = (struct SkewHeap *) malloc(sizeof(struct SkewHeap));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create SkewHeap Tree\n");
}
//return new tree
return tree;
}
// returns a new node of tree
struct TreeNode* new_node(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
//Swap the child of given node
void swap_child(struct TreeNode*parent)
{
if(parent != NULL)
{
struct TreeNode * temp = parent->left;
parent->left = parent->right;
parent->right = temp;
}
}
//Merge nodes of given two SkewHeap tree
struct TreeNode *merge_node(struct TreeNode *n1,struct TreeNode *n2)
{
if(n1==NULL)
{
return n2;
}
if(n2==NULL)
{
return n1;
}
if(n1->data < n2->data)
{
struct TreeNode * temp = n1->right;
n1->right = n1->left;
n1->left = merge_node(n2, temp);
return n1;
}
else
{
return merge_node(n2, n1);
}
}
// Handles the request of adding a new node in SkewHeap
void add_node(struct SkewHeap *tree ,int data)
{
struct TreeNode *node = new_node(data);
tree->root = merge_node(node,tree->root);
}
void inorder(struct TreeNode *node)
{
if (node!=NULL)
{
inorder(node->left);
//Print node value
printf(" %d", node->data);
inorder(node->right);
}
}
void preorder(struct TreeNode *node)
{
if (node!=NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
void postorder(struct TreeNode *node)
{
if (node!=NULL)
{
postorder(node->left);
postorder(node->right);
//Print node value
printf(" %d", node->data);
}
}
// Handles the request of view tree elements
void print_tree(struct SkewHeap *tree)
{
if(tree->root!=NULL)
{
// Display tree elements
printf("\n Preorder : ");
preorder(tree->root);
printf("\n Inorder : ");
inorder(tree->root);
printf("\n Postorder : " );
postorder(tree->root);
printf("\n");
}
else
{
printf("\n Empty Tree");
}
}
//Handles the request to merge two SkewHeap trees
void merge_tree(struct SkewHeap *tree1,struct SkewHeap *tree2)
{
tree1->root = merge_node(tree1->root,tree2->root);
tree2->root = NULL;
}
void delete_min(struct SkewHeap *tree)
{
if(tree->root==NULL)
{
printf("\nEmpty Tree\n");
}
else
{
tree->root = merge_node(tree->root->left,tree->root->right);
}
}
//Print Min element of tree
void min_element(struct SkewHeap *tree)
{
if(tree->root==NULL)
{
printf("\nEmpty Tree\n");
}
else
{
printf("\n Min Element : %d \n",tree->root->data );
}
}
int main()
{
struct SkewHeap *tree1 = new_tree();
// Added nodes
add_node(tree1, 6);
add_node(tree1, 9);
add_node(tree1, 11);
add_node(tree1, 3);
add_node(tree1, 2);
add_node(tree1, 45);
add_node(tree1, 70);
add_node(tree1, 4);
add_node(tree1, 13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
print_tree(tree1);
struct SkewHeap *tree2 = new_tree();
// Put tree nodes
add_node(tree2, 5);
add_node(tree2, 9);
add_node(tree2, 41);
add_node(tree2, 8);
add_node(tree2, 12);
add_node(tree2, 50);
add_node(tree2, 100);
add_node(tree2, 120);
add_node(tree2, 150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
print_tree(tree2);
printf("\n Merge Two Tree \n");
merge_tree(tree1,tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
printf("\n Tree 1");
print_tree(tree1);
printf("\n Tree 2");
print_tree(tree2);
printf("\n\n Delete Min ");
min_element(tree1);
delete_min(tree1);
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
print_tree(tree1);
return 0;
}
Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3/*
Java Program
Implement Skew heap
*/
// Tree Node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// SkewHeap
public class SkewHeap
{
public TreeNode root;
public SkewHeap()
{
this.root = null;
}
//Swap the child of given node
public void swap_child(TreeNode parent)
{
if (parent != null)
{
TreeNode temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
//Merge nodes of given two SkewHeap tree
public TreeNode merge_node(TreeNode n1, TreeNode n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
TreeNode temp = n1.right;
n1.right = n1.left;
n1.left = merge_node(n2, temp);
return n1;
}
else
{
return merge_node(n2, n1);
}
}
// Handles the request of adding a new node in SkewHeap tree
public void add_node(int data)
{
TreeNode node = new TreeNode(data);
this.root = merge_node(node, this.root);
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
//Print node value
System.out.print(" " + node.data);
inorder(node.right);
}
}
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
public void postorder(TreeNode node)
{
if (node != null)
{
postorder(node.left);
postorder(node.right);
//Print node value
System.out.print(" " + node.data);
}
}
// Handles the request of view tree elements
public void print_tree()
{
if (this.root != null)
{
// Display tree elements
System.out.print("\n Preorder : ");
preorder(this.root);
System.out.print("\n Inorder : ");
inorder(this.root);
System.out.print("\n Postorder : ");
postorder(this.root);
System.out.print("\n");
}
else
{
System.out.print("\n Empty Tree");
}
}
//Handles the request to merge two trees
public void merge_tree(SkewHeap tree2)
{
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
public void delete_min()
{
if (this.root == null)
{
System.out.print("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
//Print Min element of tree
public void min_element()
{
if (this.root == null)
{
System.out.print("\nEmpty Tree\n");
}
else
{
System.out.print("\n Min Element : " + this.root.data + " \n");
}
}
public static void main(String[] args)
{
SkewHeap tree1 = new SkewHeap();
SkewHeap tree2 = new SkewHeap();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree2.print_tree();
System.out.print("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
System.out.print("\n Tree 1");
tree1.print_tree();
System.out.print("\n Tree 2");
tree2.print_tree();
System.out.print("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
tree1.print_tree();
}
}Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Implement Skew heap
*/
// Tree Node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// SkewHeap
class SkewHeap
{
public: TreeNode *root;
SkewHeap()
{
this->root = NULL;
}
// Swap the child of given node
void swap_child(TreeNode *parent)
{
if (parent != NULL)
{
TreeNode *temp = parent->left;
parent->left = parent->right;
parent->right = temp;
}
}
// Merge nodes of given two SkewHeap tree
TreeNode *merge_node(TreeNode *n1, TreeNode *n2)
{
if (n1 == NULL)
{
return n2;
}
if (n2 == NULL)
{
return n1;
}
if (n1->data < n2->data)
{
TreeNode *temp = n1->right;
n1->right = n1->left;
n1->left = this->merge_node(n2, temp);
return n1;
}
else
{
return this->merge_node(n2, n1);
}
}
// Handles the request of adding a new node in SkewHeap tree
void add_node(int data)
{
TreeNode *node = new TreeNode(data);
this->root = this->merge_node(node, this->root);
}
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
// Print node value
cout << " " << node->data;
this->inorder(node->right);
}
}
void preorder(TreeNode *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
void postorder(TreeNode *node)
{
if (node != NULL)
{
this->postorder(node->left);
this->postorder(node->right);
// Print node value
cout << " " << node->data;
}
}
// Handles the request of view tree elements
void print_tree()
{
if (this->root != NULL)
{
// Display tree elements
cout << "\n Preorder : ";
this->preorder(this->root);
cout << "\n Inorder : ";
this->inorder(this->root);
cout << "\n Postorder : ";
this->postorder(this->root);
cout << "\n";
}
else
{
cout << "\n Empty Tree";
}
}
// Handles the request to merge two trees
void merge_tree(SkewHeap &tree2)
{
this->root = this->merge_node(this->root, tree2.root);
tree2.root = NULL;
}
void delete_min()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n";
}
else
{
this->root = this->merge_node(this->root->left, this->root->right);
}
}
// Print Min element of tree
void min_element()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n";
}
else
{
cout << "\n Min Element : " << this->root->data << " \n";
}
}
};
int main()
{
SkewHeap tree1 = SkewHeap();
SkewHeap tree2 = SkewHeap();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree2.print_tree();
cout << "\n Merge Two Tree \n";
tree1.merge_tree(tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
cout << "\n Tree 1";
tree1.print_tree();
cout << "\n Tree 2";
tree2.print_tree();
cout << "\n\n Delete Min ";
tree1.min_element();
tree1.delete_min();
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
tree1.print_tree();
return 0;
}Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3// Include namespace system
using System;
/*
C# Program
Implement Skew heap
*/
// Tree Node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// SkewHeap
public class SkewHeap
{
public TreeNode root;
public SkewHeap()
{
this.root = null;
}
// Swap the child of given node
public void swap_child(TreeNode parent)
{
if (parent != null)
{
TreeNode temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two SkewHeap tree
public TreeNode merge_node(TreeNode n1, TreeNode n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
TreeNode temp = n1.right;
n1.right = n1.left;
n1.left = merge_node(n2, temp);
return n1;
}
else
{
return merge_node(n2, n1);
}
}
// Handles the request of adding a new node in SkewHeap tree
public void add_node(int data)
{
TreeNode node = new TreeNode(data);
this.root = merge_node(node, this.root);
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
// Print node value
Console.Write(" " + node.data);
inorder(node.right);
}
}
public void preorder(TreeNode node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
public void postorder(TreeNode node)
{
if (node != null)
{
postorder(node.left);
postorder(node.right);
// Print node value
Console.Write(" " + node.data);
}
}
// Handles the request of view tree elements
public void print_tree()
{
if (this.root != null)
{
// Display tree elements
Console.Write("\n Preorder : ");
preorder(this.root);
Console.Write("\n Inorder : ");
inorder(this.root);
Console.Write("\n Postorder : ");
postorder(this.root);
Console.Write("\n");
}
else
{
Console.Write("\n Empty Tree");
}
}
// Handles the request to merge two trees
public void merge_tree(SkewHeap tree2)
{
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
public void delete_min()
{
if (this.root == null)
{
Console.Write("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
public void min_element()
{
if (this.root == null)
{
Console.Write("\nEmpty Tree\n");
}
else
{
Console.Write("\n Min Element : " + this.root.data + " \n");
}
}
public static void Main(String[] args)
{
SkewHeap tree1 = new SkewHeap();
SkewHeap tree2 = new SkewHeap();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree2.print_tree();
Console.Write("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
Console.Write("\n Tree 1");
tree1.print_tree();
Console.Write("\n Tree 2");
tree2.print_tree();
Console.Write("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
tree1.print_tree();
}
}Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3<?php
/*
Php Program
Implement Skew heap
*/
// Tree Node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// SkewHeap
class SkewHeap
{
public $root;
function __construct()
{
$this->root = null;
}
// Swap the child of given node
public function swap_child($parent)
{
if ($parent != null)
{
$temp = $parent->left;
$parent->left = $parent->right;
$parent->right = $temp;
}
}
// Merge nodes of given two SkewHeap tree
public function merge_node($n1, $n2)
{
if ($n1 == null)
{
return $n2;
}
if ($n2 == null)
{
return $n1;
}
if ($n1->data < $n2->data)
{
$temp = $n1->right;
$n1->right = $n1->left;
$n1->left = $this->merge_node($n2, $temp);
return $n1;
}
else
{
return $this->merge_node($n2, $n1);
}
}
// Handles the request of adding a new node in SkewHeap tree
public function add_node($data)
{
$node = new TreeNode($data);
$this->root = $this->merge_node($node, $this->root);
}
public function inorder($node)
{
if ($node != null)
{
$this->inorder($node->left);
// Print node value
echo " ". $node->data;
$this->inorder($node->right);
}
}
public function preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
public function postorder($node)
{
if ($node != null)
{
$this->postorder($node->left);
$this->postorder($node->right);
// Print node value
echo " ". $node->data;
}
}
// Handles the request of view tree elements
public function print_tree()
{
if ($this->root != null)
{
// Display tree elements
echo "\n Preorder : ";
$this->preorder($this->root);
echo "\n Inorder : ";
$this->inorder($this->root);
echo "\n Postorder : ";
$this->postorder($this->root);
echo "\n";
}
else
{
echo "\n Empty Tree";
}
}
// Handles the request to merge two trees
public function merge_tree($tree2)
{
$this->root = $this->merge_node($this->root, $tree2->root);
$tree2->root = null;
}
public function delete_min()
{
if ($this->root == null)
{
echo "\nEmpty Tree\n";
}
else
{
$this->root = $this->merge_node($this->root->left, $this->root->right);
}
}
// Print Min element of tree
public function min_element()
{
if ($this->root == null)
{
echo "\nEmpty Tree\n";
}
else
{
echo "\n Min Element : ". $this->root->data ." \n";
}
}
}
function main()
{
$tree1 = new SkewHeap();
$tree2 = new SkewHeap();
// Added nodes
$tree1->add_node(6);
$tree1->add_node(9);
$tree1->add_node(11);
$tree1->add_node(3);
$tree1->add_node(2);
$tree1->add_node(45);
$tree1->add_node(70);
$tree1->add_node(4);
$tree1->add_node(13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
$tree1->print_tree();
// Put tree nodes
$tree2->add_node(5);
$tree2->add_node(9);
$tree2->add_node(41);
$tree2->add_node(8);
$tree2->add_node(12);
$tree2->add_node(50);
$tree2->add_node(100);
$tree2->add_node(120);
$tree2->add_node(150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
$tree2->print_tree();
echo "\n Merge Two Tree \n";
$tree1->merge_tree($tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
echo "\n Tree 1";
$tree1->print_tree();
echo "\n Tree 2";
$tree2->print_tree();
echo "\n\n Delete Min ";
$tree1->min_element();
$tree1->delete_min();
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
$tree1->print_tree();
}
main();Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3/*
Node Js Program
Implement Skew heap
*/
// Tree Node
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// SkewHeap
class SkewHeap
{
constructor()
{
this.root = null;
}
// Swap the child of given node
swap_child(parent)
{
if (parent != null)
{
var temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two SkewHeap tree
merge_node(n1, n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
var temp = n1.right;
n1.right = n1.left;
n1.left = this.merge_node(n2, temp);
return n1;
}
else
{
return this.merge_node(n2, n1);
}
}
// Handles the request of adding a new node in SkewHeap tree
add_node(data)
{
var node = new TreeNode(data);
this.root = this.merge_node(node, this.root);
}
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
// Print node value
process.stdout.write(" " + node.data);
this.inorder(node.right);
}
}
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
postorder(node)
{
if (node != null)
{
this.postorder(node.left);
this.postorder(node.right);
// Print node value
process.stdout.write(" " + node.data);
}
}
// Handles the request of view tree elements
print_tree()
{
if (this.root != null)
{
// Display tree elements
process.stdout.write("\n Preorder : ");
this.preorder(this.root);
process.stdout.write("\n Inorder : ");
this.inorder(this.root);
process.stdout.write("\n Postorder : ");
this.postorder(this.root);
process.stdout.write("\n");
}
else
{
process.stdout.write("\n Empty Tree");
}
}
// Handles the request to merge two trees
merge_tree(tree2)
{
this.root = this.merge_node(this.root, tree2.root);
tree2.root = null;
}
delete_min()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n");
}
else
{
this.root = this.merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
min_element()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n");
}
else
{
process.stdout.write("\n Min Element : " + this.root.data + " \n");
}
}
}
function main()
{
var tree1 = new SkewHeap();
var tree2 = new SkewHeap();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree2.print_tree();
process.stdout.write("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
process.stdout.write("\n Tree 1");
tree1.print_tree();
process.stdout.write("\n Tree 2");
tree2.print_tree();
process.stdout.write("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
tree1.print_tree();
}
main();Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3# Python 3 Program
# Implement Skew heap
# Tree Node
class TreeNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
# SkewHeap
class SkewHeap :
def __init__(self) :
self.root = None
# Swap the child of given node
def swap_child(self, parent) :
if (parent != None) :
temp = parent.left
parent.left = parent.right
parent.right = temp
# Merge nodes of given two SkewHeap tree
def merge_node(self, n1, n2) :
if (n1 == None) :
return n2
if (n2 == None) :
return n1
if (n1.data < n2.data) :
temp = n1.right
n1.right = n1.left
n1.left = self.merge_node(n2, temp)
return n1
else :
return self.merge_node(n2, n1)
# Handles the request of adding a new node in SkewHeap tree
def add_node(self, data) :
node = TreeNode(data)
self.root = self.merge_node(node, self.root)
def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.inorder(node.right)
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
def postorder(self, node) :
if (node != None) :
self.postorder(node.left)
self.postorder(node.right)
# Print node value
print(" ", node.data, end = "")
# Handles the request of view tree elements
def print_tree(self) :
if (self.root != None) :
# Display tree elements
print("\n Preorder : ", end = "")
self.preorder(self.root)
print("\n Inorder : ", end = "")
self.inorder(self.root)
print("\n Postorder : ", end = "")
self.postorder(self.root)
print("\n", end = "")
else :
print("\n Empty Tree", end = "")
# Handles the request to merge two trees
def merge_tree(self, tree2) :
self.root = self.merge_node(self.root, tree2.root)
tree2.root = None
def delete_min(self) :
if (self.root == None) :
print("\nEmpty Tree\n", end = "")
else :
self.root = self.merge_node(self.root.left, self.root.right)
# Print Min element of tree
def min_element(self) :
if (self.root == None) :
print("\nEmpty Tree\n", end = "")
else :
print("\n Min Element : ", self.root.data ," \n", end = "")
def main() :
tree1 = SkewHeap()
tree2 = SkewHeap()
# Added nodes
tree1.add_node(6)
tree1.add_node(9)
tree1.add_node(11)
tree1.add_node(3)
tree1.add_node(2)
tree1.add_node(45)
tree1.add_node(70)
tree1.add_node(4)
tree1.add_node(13)
#
# 2
# / \
# / \
# 3 4
# / \ /
# 6 70 45
# / \
# 9 11
# /
# 13
# ----------------------------
# Constructing Binary Swap heap tree
# ----------------------------
#
tree1.print_tree()
# Put tree nodes
tree2.add_node(5)
tree2.add_node(9)
tree2.add_node(41)
tree2.add_node(8)
tree2.add_node(12)
tree2.add_node(50)
tree2.add_node(100)
tree2.add_node(120)
tree2.add_node(150)
#
# 5
# / \
# / \
# 12 8
# / \ / \
# 41 100 9 50
# / /
# 150 120
# ----------------------------
# Constructing Binary Swap heap tree
# ----------------------------
#
tree2.print_tree()
print("\n Merge Two Tree \n", end = "")
tree1.merge_tree(tree2)
#
# After merge two tree
# 2
# / \
# / \
# / \
# / \
# / \
# / \
# / \
# 4 3
# / \ / \
# / \ / \
# 5 45 6 70
# / \ / \
# / \ / \
# 12 8 9 11
# / \ / \ /
# 41 100 9 50 13
# / /
# 150 120
# -------------------------------------
#
print("\n Tree 1", end = "")
tree1.print_tree()
print("\n Tree 2", end = "")
tree2.print_tree()
print("\n\n Delete Min ", end = "")
tree1.min_element()
tree1.delete_min()
#
# --------------------------
# After Delete min element [2]
# --------------------------
# 3
# / \
# / \
# / \
# / \
# / \
# / \
# / \
# 4 6
# / \ / \
# / \ / \
# 45 5 9 11
# / / \ /
# / / \ /
# 70 12 8 13
# / \ / \
# 41 100 9 50
# / /
# 150 120
# -------------------------------------
#
tree1.print_tree()
if __name__ == "__main__": main()Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3# Ruby Program
# Implement Skew heap
# Tree Node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
# SkewHeap
class SkewHeap
# Define the accessor and reader of class SkewHeap
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Swap the child of given node
def swap_child(parent)
if (parent != nil)
temp = parent.left
parent.left = parent.right
parent.right = temp
end
end
# Merge nodes of given two SkewHeap tree
def merge_node(n1, n2)
if (n1 == nil)
return n2
end
if (n2 == nil)
return n1
end
if (n1.data < n2.data)
temp = n1.right
n1.right = n1.left
n1.left = self.merge_node(n2, temp)
return n1
else
return self.merge_node(n2, n1)
end
end
# Handles the request of adding a new node in SkewHeap tree
def add_node(data)
node = TreeNode.new(data)
self.root = self.merge_node(node, self.root)
end
def inorder(node)
if (node != nil)
self.inorder(node.left)
# Print node value
print(" ", node.data)
self.inorder(node.right)
end
end
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
def postorder(node)
if (node != nil)
self.postorder(node.left)
self.postorder(node.right)
# Print node value
print(" ", node.data)
end
end
# Handles the request of view tree elements
def print_tree()
if (self.root != nil)
# Display tree elements
print("\n Preorder : ")
self.preorder(self.root)
print("\n Inorder : ")
self.inorder(self.root)
print("\n Postorder : ")
self.postorder(self.root)
print("\n")
else
print("\n Empty Tree")
end
end
# Handles the request to merge two trees
def merge_tree(tree2)
self.root = self.merge_node(self.root, tree2.root)
tree2.root = nil
end
def delete_min()
if (self.root == nil)
print("\nEmpty Tree\n")
else
self.root = self.merge_node(self.root.left, self.root.right)
end
end
# Print Min element of tree
def min_element()
if (self.root == nil)
print("\nEmpty Tree\n")
else
print("\n Min Element : ", self.root.data ," \n")
end
end
end
def main()
tree1 = SkewHeap.new()
tree2 = SkewHeap.new()
# Added nodes
tree1.add_node(6)
tree1.add_node(9)
tree1.add_node(11)
tree1.add_node(3)
tree1.add_node(2)
tree1.add_node(45)
tree1.add_node(70)
tree1.add_node(4)
tree1.add_node(13)
#
# 2
# / \
# / \
# 3 4
# / \ /
# 6 70 45
# / \
# 9 11
# /
# 13
# ----------------------------
# Constructing Binary Swap heap tree
# ----------------------------
#
tree1.print_tree()
# Put tree nodes
tree2.add_node(5)
tree2.add_node(9)
tree2.add_node(41)
tree2.add_node(8)
tree2.add_node(12)
tree2.add_node(50)
tree2.add_node(100)
tree2.add_node(120)
tree2.add_node(150)
#
# 5
# / \
# / \
# 12 8
# / \ / \
# 41 100 9 50
# / /
# 150 120
# ----------------------------
# Constructing Binary Swap heap tree
# ----------------------------
#
tree2.print_tree()
print("\n Merge Two Tree \n")
tree1.merge_tree(tree2)
#
# After merge two tree
# 2
# / \
# / \
# / \
# / \
# / \
# / \
# / \
# 4 3
# / \ / \
# / \ / \
# 5 45 6 70
# / \ / \
# / \ / \
# 12 8 9 11
# / \ / \ /
# 41 100 9 50 13
# / /
# 150 120
# -------------------------------------
#
print("\n Tree 1")
tree1.print_tree()
print("\n Tree 2")
tree2.print_tree()
print("\n\n Delete Min ")
tree1.min_element()
tree1.delete_min()
#
# --------------------------
# After Delete min element [2]
# --------------------------
# 3
# / \
# / \
# / \
# / \
# / \
# / \
# / \
# 4 6
# / \ / \
# / \ / \
# 45 5 9 11
# / / \ /
# / / \ /
# 70 12 8 13
# / \ / \
# 41 100 9 50
# / /
# 150 120
# -------------------------------------
#
tree1.print_tree()
end
main()Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3
/*
Scala Program
Implement Skew heap
*/
// Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// SkewHeap
class SkewHeap(var root: TreeNode)
{
def this()
{
this(null);
}
// Swap the child of given node
def swap_child(parent: TreeNode): Unit = {
if (parent != null)
{
var temp: TreeNode = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two SkewHeap tree
def merge_node(n1: TreeNode, n2: TreeNode): TreeNode = {
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
var temp: TreeNode = n1.right;
n1.right = n1.left;
n1.left = merge_node(n2, temp);
return n1;
}
else
{
return merge_node(n2, n1);
}
}
// Handles the request of adding a new node in SkewHeap tree
def add_node(data: Int): Unit = {
var node: TreeNode = new TreeNode(data);
this.root = merge_node(node, this.root);
}
def inorder(node: TreeNode): Unit = {
if (node != null)
{
inorder(node.left);
// Print node value
print(" " + node.data);
inorder(node.right);
}
}
def preorder(node: TreeNode): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
def postorder(node: TreeNode): Unit = {
if (node != null)
{
postorder(node.left);
postorder(node.right);
// Print node value
print(" " + node.data);
}
}
// Handles the request of view tree elements
def print_tree(): Unit = {
if (this.root != null)
{
// Display tree elements
print("\n Preorder : ");
preorder(this.root);
print("\n Inorder : ");
inorder(this.root);
print("\n Postorder : ");
postorder(this.root);
print("\n");
}
else
{
print("\n Empty Tree");
}
}
// Handles the request to merge two trees
def merge_tree(tree2: SkewHeap): Unit = {
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
def delete_min(): Unit = {
if (this.root == null)
{
print("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
def min_element(): Unit = {
if (this.root == null)
{
print("\nEmpty Tree\n");
}
else
{
print("\n Min Element : " + this.root.data + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: SkewHeap = new SkewHeap();
var tree2: SkewHeap = new SkewHeap();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree2.print_tree();
print("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
print("\n Tree 1");
tree1.print_tree();
print("\n Tree 2");
tree2.print_tree();
print("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
tree1.print_tree();
}
}Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3/*
Swift 4 Program
Implement Skew heap
*/
// Tree Node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
// SkewHeap
class SkewHeap
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Swap the child of given node
func swap_child(_ parent: TreeNode? )
{
if (parent != nil)
{
let temp: TreeNode? = parent!.left;
parent!.left = parent!.right;
parent!.right = temp;
}
}
// Merge nodes of given two SkewHeap tree
func merge_node(_ n1: TreeNode? , _ n2 : TreeNode? )->TreeNode?
{
if (n1 == nil)
{
return n2;
}
if (n2 == nil)
{
return n1;
}
if (n1!.data < n2!.data)
{
let temp: TreeNode? = n1!.right;
n1!.right = n1!.left;
n1!.left = self.merge_node(n2, temp);
return n1;
}
else
{
return self.merge_node(n2, n1);
}
}
// Handles the request of adding a new node in SkewHeap tree
func add_node(_ data: Int)
{
let node: TreeNode? = TreeNode(data);
self.root = self.merge_node(node, self.root);
}
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
self.inorder(node!.left);
// Print node value
print(" ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
func preorder(_ node: TreeNode? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func postorder(_ node: TreeNode? )
{
if (node != nil)
{
self.postorder(node!.left);
self.postorder(node!.right);
// Print node value
print(" ", node!.data, terminator: "");
}
}
// Handles the request of view tree elements
func print_tree()
{
if (self.root != nil)
{
// Display tree elements
print("\n Preorder : ", terminator: "");
self.preorder(self.root);
print("\n Inorder : ", terminator: "");
self.inorder(self.root);
print("\n Postorder : ", terminator: "");
self.postorder(self.root);
print("\n", terminator: "");
}
else
{
print("\n Empty Tree", terminator: "");
}
}
// Handles the request to merge two trees
func merge_tree(_ tree2: SkewHeap? )
{
self.root = self.merge_node(self.root, tree2!.root);
tree2!.root = nil;
}
func delete_min()
{
if (self.root == nil)
{
print("\nEmpty Tree\n", terminator: "");
}
else
{
self.root = self.merge_node(self.root!.left, self.root!.right);
}
}
// Print Min element of tree
func min_element()
{
if (self.root == nil)
{
print("\nEmpty Tree\n", terminator: "");
}
else
{
print("\n Min Element : ", self.root!.data ," \n", terminator: "");
}
}
}
func main()
{
let tree1: SkewHeap = SkewHeap();
let tree2: SkewHeap = SkewHeap();
// Added nodes
tree1.add_node(6);
tree1.add_node(9);
tree1.add_node(11);
tree1.add_node(3);
tree1.add_node(2);
tree1.add_node(45);
tree1.add_node(70);
tree1.add_node(4);
tree1.add_node(13);
/*
2
/ \
/ \
3 4
/ \ /
6 70 45
/ \
9 11
/
13
----------------------------
Constructing Binary Swap heap tree
----------------------------
*/
tree1.print_tree();
// Put tree nodes
tree2.add_node(5);
tree2.add_node(9);
tree2.add_node(41);
tree2.add_node(8);
tree2.add_node(12);
tree2.add_node(50);
tree2.add_node(100);
tree2.add_node(120);
tree2.add_node(150);
/*
5
/ \
/ \
12 8
/ \ / \
41 100 9 50
/ /
150 120
--------------------------------------
Constructing Binary Swap heap tree
--------------------------------------
*/
tree2.print_tree();
print("\n Merge Two Tree \n", terminator: "");
tree1.merge_tree(tree2);
/*
After merge two tree
2
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / \
5 45 6 70
/ \ / \
/ \ / \
12 8 9 11
/ \ / \ /
41 100 9 50 13
/ /
150 120
-------------------------------------
*/
print("\n Tree 1", terminator: "");
tree1.print_tree();
print("\n Tree 2", terminator: "");
tree2.print_tree();
print("\n\n Delete Min ", terminator: "");
tree1.min_element();
tree1.delete_min();
/*
--------------------------
After Delete min element [2]
--------------------------
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 6
/ \ / \
/ \ / \
45 5 9 11
/ / \ /
/ / \ /
70 12 8 13
/ \ / \
41 100 9 50
/ /
150 120
-------------------------------------
*/
tree1.print_tree();
}
main();Output
Preorder : 2 3 6 9 13 11 70 4 45
Inorder : 13 9 6 11 3 70 2 45 4
Postorder : 13 9 11 6 70 3 45 4 2
Preorder : 5 12 41 150 100 8 9 120 50
Inorder : 150 41 12 100 5 120 9 8 50
Postorder : 150 41 100 12 120 9 50 8 5
Merge Two Tree
Tree 1
Preorder : 2 4 5 12 41 150 100 8 9 120 50 45 3 6 9 13 11 70
Inorder : 150 41 12 100 5 120 9 8 50 4 45 2 13 9 6 11 3 70
Postorder : 150 41 100 12 120 9 50 8 5 45 4 13 9 11 6 70 3 2
Tree 2
Empty Tree
Delete Min
Min Element : 2
Preorder : 3 4 45 70 5 12 41 150 100 8 9 120 50 6 9 13 11
Inorder : 70 45 4 150 41 12 100 5 120 9 8 50 3 13 9 6 11
Postorder : 70 45 150 41 100 12 120 9 50 8 5 4 13 9 11 6 3
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment