n=n+1; // n is incremented to insert the new element

A[n]=value; // assign new value at the nth position

i = n; // assign the value of n to i
// loop will be executed until i becomes 1.
while(i>1)
{ parent= floor value of i/2; // Calculating the floor value of i/2
// Condition to check whether the value of parent is less than the given node or not
if(A[parent]<A[i])
{
swap(A[parent], A[i]);
i = parent;
}
else
{
return;
}
}
}

Heapify

Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-
Heap or a Max-Heap.

Algorithm to heapify the tree

MaxHeapify(A, n, i)
{
int largest =i;
int l= 2i;
int r= 2i+1;
while(l<=n && A[l]>A[largest])
{
largest=l;
}
Prajyoti Niketan College- Pudukad Department of Computer Science
 while(r<=n && A[r]>A[largest])
{
largest=r;
}
if(largest!=i)
{
swap(A[largest], A[i]);
heapify(A, n, largest);
}}

Peek (Find max/min)

Peek operation returns the maximum element from Max Heap or minimum element from Min Heap

without deleting the node.

For both Max heap and Min Heap

return rootNode

Extract-Max/Min

Extract-Max returns the node with maximum value after removing it from a Max Heap whereas

Extract-Min returns the node with minimum after removing it from Min Heap.

Time complexity Analysis

1. Complexity Analysis of Insert operation in Max Heap

When a node is supposed to add into the heap, the element is added at the next vacant index of the
array. Then it is checked whether the inserted child node is in accordance with the parent node or
not. If the child has a higher value than the parent, the swapping of the nodes is done. This
swapping process goes on until the properties of Max Heap are fulfilled.

Complexity of adding a node is: O(1)

Complexity of swapping the nodes(heapify): O(H) [where H is height of the tree]
(swapping will be done H times in the worst case scenario)
Prajyoti Niketan College- Pudukad Department of Computer Science
Total complexity: O(1) + O(H) = O(H)
For a Complete Binary tree, its height H = O(log N), where N represents total no. of nodes.

Therefore, Overall Complexity of insert operation is O(log N).

2. Complexity Analysis of Delete operation in min heap

Deletion of a node cannot be done randomly. The element with the highest priority (i.e. parent) will
be deleted first followed by the next node in order of priority. This is why heap is called a priority
queue.

First, swap the positions of the parent node and leaf node, and then remove the newly formed leaf
node (which was originally the parent) from the queue. Next, start the swapping process so that the
new parent node is placed in the right position in accordance with the properties of Min Heap.

If a node is to be deleted from a heap with height H:

Complexity of swapping parent node and leaf node is: O(1)

Complexity of swapping the nodes(heapify): O(H)
(swapping will be done H times in the worst case scenario)
Total complexity: O(1) + O(H) = O(H)
For a Complete Binary tree, its height H = O(log N), where N represents total no. of nodes.

Therefore, Overall Complexity of delete operation is O(log N).

3. Complexity of getting the Maximum value from max heap

In order to obtain the maximum value just return the value of the root node
(which is the greatest element in Max Heap), so simply return the element at
index 0 of the array.

Hence, Complexity of getting minimum value is: O(1)

Deaps (double-ended-priority-queues:
deaps)
Prajyoti Niketan College- Pudukad Department of Computer Science
Deap is defined as a data structure which has no element or key value at the root node.

It is formed by implementing the following rules −

● There is no element at root node that indicates root node is empty.

● Left subtree of the deap shall indicate min heap.
● Right subtree of deap shall indicate max heap.

A deap is a complete binary tree that is either empty or satisfies the following conditions:

1. The root is empty.

2. The left subtree is a min heap and the right subtree is a max heap.

3. Correspondence property. Suppose that the right subtree is not empty. For every
node x in the left subtree, define its corresponding node y in the right subtree to be the

node in the same position as x. In case such a y doesn’t exist, let y be the corresponding
node for the parent of x. The element in x is ≤ the element in y.

Thus, correctness to the following statement can be provided mathematically by a deap

structure −

If the left sub tree and right sub tree of certain nodes are non-empty, and their

corresponding nodes can be represented by ‘a’ and ‘b’ respectively, then −

[Link] <= [Link]

Correspondence property

The complete binary tree above , the corresponding nodes for the nodes with
3,7,5,9,15,11,12, respectively have 20,18,16,10,18,16, and 16.

Inserting an element in a deap

When an element is inserted into an n-element deap , we go from a complete binary
tree that has n+1 nodes to one that has n+2 nodes. So the shape of the new deap is
well defined.
The new node is j and its corresponding node is i.
To insert new element temporarily place new element into the new node j and check the
correspondence property for node j. If the property is not satisfied, swap new element

Prajyoti Niketan College- Pudukad Department of Computer Science

and the element in its corresponding node ; use a trickle up process to correctly position
new element in the heap for the corresponding node i. If the correspondence property is
satisfied, do not swap new element ; instead use a trickle up process to correctly place
new element in the heap that contains node j.
That is;
1. Consider the insertion of new element ‘2’ into our deap.
2. The element in the corresponding node ‘i’ is 15
3. Since the correspondence property is not satisfied, we swap 2 and 15

4. Node j now contains 15 and this swap is guaranteed to preserve the max heap
properties of the right subtree of the complete binary tree
5. To correctly position the 2 in the left subtree , we use the standard min heap trickle
process beginning at node ‘i’ .
This is how the result will look like,

Deletion of the min element

Assume that n>0 .The min element is in the root of the min heap. Following its removal ,
the deap size reduces to n-1 and the element in position n+1 of the deap array is dropped
from the deap.

In our example, the min element 3 is removed and 10 is dropped. To reinsert the dropped
element we first trickle the vacancy in the root of the min heap down to a leaf of the min
heap. The trickle down causes 5 and 11 to, respectively, move to their present nodes.
Then the dropped element 10 is inserted using a trickle up process beginning at the
vacant leaf of the min heap. Since a remove min requires a trickle – down pass followed
by a trickle – up pass and since the height of a deap is O(log n), the time for a remove
min is O(log n).

Splay Tree Data structure

Splay tree is another variant of a binary search tree. In a splay tree, recently accessed element is

placed at the root of the tree. A splay tree is defined as follows...

Splay Tree is a self - adjusted Binary Search Tree in which every operation on element

rearranges the tree so that the element is placed at the root position of the tree.

Prajyoti Niketan College- Pudukad Department of Computer Science

In a splay tree, every operation is performed at the root of the tree. All the operations in splay tree are

involved with a common operation called "Splaying".

Splaying an element, is the process of bringing it to the root position by performing suitable

rotation operations.

Ø In a splay tree, splaying an element rearranges all the elements in the tree so that splayed

element is placed at the root of the tree.

Ø By splaying elements we bring more frequently used elements closer to the root of the tree

so that any operation on those elements is performed quickly. That means the splaying

operation automatically brings more frequently used elements closer to the root of the

tree.

Every operation on splay tree performs the splaying operation. For example, the insertion

operation first inserts the new element using the binary search tree insertion process,

then the newly inserted element is splayed so that it is placed at the root of the tree.

Ø The search operation in a splay tree is nothing but searching the element using binary

search process and then splaying that searched element so that it is placed at the root of

the tree.

In splay tree, to splay any element we use the following rotation operations...

Rotations in Splay Tree

● 1. Zig Rotation

● 2. Zag Rotation

● 3. Zig - Zig Rotation

● 4. Zag - Zag Rotation

Prajyoti Niketan College- Pudukad Department of Computer Science

 ● 5. Zig - Zag Rotation

● 6. Zag - Zig Rotation

Factors required for selecting a type of rotation

The following are the factors used for selecting a type of rotation:

● Does the node which we are trying to rotate have a grandparent?

● Is the node left or right child of the parent?

● Is the node left or right child of the grandparent?

Cases for the Rotations

Case 1: If the node does not have a grand-parent, and if it is the right child of the parent, then
we carry out the left rotation; otherwise, the right rotation is performed.

Case 2: If the node has a grandparent, then based on the following scenarios; the rotation
would be performed:

Scenario 1: If the node is the right of the parent and the parent is also right of its parent, then
zag zag left left rotation is performed.

Scenario 2: If the node is left of a parent, but the parent is right of its parent, then zig zag right
left rotation is performed.

Scenario 3: If the node is left of the parent and the parent is left of its parent, then zig zig right
right rotation is performed.

Scenario 4: If the node is right of a parent, but the parent is left of its parent, then zag zig left
right rotation is performed.

Zig Rotation
The Zig Rotation in splay tree is similar to the single right rotation in AVL Tree rotations. In zig rotation,

every node moves one position to the right from its current position. Consider the following example...

Zag Rotation

Prajyoti Niketan College- Pudukad Department of Computer Science

The Zag Rotation in splay tree is similar to the single left rotation in AVL Tree rotations. In zag rotation,

every node moves one position to the left from its current position. Consider the following example...

Zig-Zig Rotation
The Zig-Zig Rotation in splay tree is a double zig rotation. In zig-zig rotation, every node moves two

positions to the right from its current position. Consider the following example...

Zag-Zag Rotation
The Zag-Zag Rotation in splay tree is a double zag rotation. In zag-zag rotation, every node moves

two positions to the left from its current position. Consider the following example...

Zig-Zag Rotation
The Zig-Zag Rotation in splay tree is a sequence of zig rotation followed by zag rotation. In zig-zag

rotation, every node moves one position to the right followed by one position to the left from its current

position. Consider the following example...

Zag-Zig Rotation
The Zag-Zig Rotation in splay tree is a sequence of zag rotation followed by zig rotation. In zag-zig

rotation, every node moves one position to the left followed by one position to the right from its current

position. Consider the following example...

Every Splay tree must be a binary search tree but it is need not to be balanced tree.

Prajyoti Niketan College- Pudukad Department of Computer Science

Insertion Operation in Splay Tree
The insertion operation in Splay tree is performed using following steps...

● Step 1 - Check whether tree is Empty.

● Step 2 - If tree is Empty then insert the newNode as Root node and exit from the operation.

● Step 3 - If tree is not Empty then insert the newNode as leaf node using Binary Search tree

insertion logic.

● Step 4 - After insertion, Splay the newNode

Deletion Operation in Splay Tree

The deletion operation in splay tree is similar to deletion operation in Binary Search Tree. But before

deleting the element, we first need to splay that element and then delete it from the root position.

Finally join the remaining tree using binary search tree logic.

Complexity
As we already know, the time complexity of a binary search tree in every case. The time
complexity of a binary search tree in the average case is O(logn) and the time complexity in the
worst case is O(n). In a binary search tree, the value of the left subtree is smaller than the root
node, and the value of the right subtree is greater than the root node; in such case, the time
complexity would be O(logn). If the binary tree is left-skewed or right-skewed, then the time
complexity would be O(n). To limit the skewness, the AVL and Red-Black tree came into the
picture, having O(logn) time complexity for all the operations in all the cases. We can also improve
this time complexity by doing more practical implementations, so the new Tree data structure was
designed, known as a Splay tree.

Advantages of Splay tree

● In the splay tree, we do not need to store the extra information. In contrast, in
AVL trees, we need to store the balance factor of each node that requires extra
space, and Red-Black trees also require to store one extra bit of information that
denotes the color of the node, either Red or Black.
Prajyoti Niketan College- Pudukad Department of Computer Science
 ● It is the fastest type of Binary Search tree for various practical applications. It is
used in Windows NT and GCC compilers.
● It provides better performance as the frequently accessed nodes will move
nearer to the root node, due to which the elements can be accessed quickly in
splay trees. It is used in the cache implementation as the recently accessed data
is stored in the cache so that we do not need to go to the memory for accessing
the data, and it takes less time.

Drawback of Splay tree

The major drawback of the splay tree would be that trees are not strictly balanced, i.e., they are
roughly balanced. Sometimes the splay trees are linear, so it will take O(n) time complexity.

Example - Insertion operation in Splay tree

In the insertion operation, we first insert the element in the tree and then perform the splaying
operation on the inserted element.

15, 10, 17, 7

Step 1: First, we insert node 15 in the tree. After insertion, we need to perform splaying. As 15
is a root node, so we do not need to perform splaying.

Step 2: The next element is 10. As 10 is less than 15, so node 10 will be the left child of node
15, as shown below:

Now, we perform splaying. To make 10 as a root node, we will perform the right rotation, as
shown below:

Step 3: The next element is 17. As 17 is greater than 10 and 15 so it will become the right child
of node 15.

Now, we will perform splaying. As 17 is having a parent as well as a grandparent so we will

perform zag zag rotations.

In the above figure, we can observe that 17 becomes the root node of the tree; therefore, the
insertion is completed.

Step 4: The next element is 7. As 7 is less than 17, 15, and 10, so node 7 will be left child of 10.
Prajyoti Niketan College- Pudukad Department of Computer Science
Now, we have to splay the tree. As 7 is having a parent as well as a grandparent so we will
perform two right rotations as shown below:

Still the node 7 is not a root node, it is a left child of the root node, i.e., 17. So, we need to
perform one more right rotation to make node 7 as a root node as shown below:

Algorithm for Insertion operation

1. Insert(T, n)
2. temp= T_root
3. y=NULL
4. while(temp!=NULL)
5. y=temp
6. if(n->data <temp->data)
7. temp=temp->left
8. else
9. temp=temp->right
10. [Link]= y
11. if(y==NULL)
12. T_root = n
13. else if (n->data < y->data)
14. y->left = n
15. else
16. y->right = n
17. Splay(T, n)

In the above algorithm, T is the tree and n is the node which we want to insert. We have created
a temp variable that contains the address of the root node. We will run the while loop until the
value of temp becomes NULL.

Once the insertion is completed, splaying would be performed

Algorithm for Splaying operation

1. Splay(T, N)

Prajyoti Niketan College- Pudukad Department of Computer Science

 2. while(n->parent !=Null)
3. if(n->parent==T->root)
4. if(n==n->parent->left)
5. right_rotation(T, n->parent)
6. else
7. left_rotation(T, n->parent)
8. else
9. p= n->parent
10. g = p->parent
11. if(n=n->parent->left && p=p->parent->left)
12. [Link](T, g), [Link](T, p)
13. else if(n=n->parent->right && p=p->parent->right)
14. [Link](T, g), [Link](T, p)
15. else if(n=n->parent->left && p=p->parent->right)
16. [Link](T, p), [Link](T, g)
17. else
18. [Link](T, p), [Link](T, g)
19.
20. Implementation of [Link](T, x)
21. [Link](T, x)
22. y= x->left
23. x->left=y->right
24. y->right=x
25. return y

In the above implementation, x is the node on which the rotation is performed, whereas y is the
left child of the node x.

Implementation of [Link](T, x)

1. [Link](T, x)
Prajyoti Niketan College- Pudukad Department of Computer Science
 2. y=x->right
3. x->right = y->left
4. y->left = x
5. return y

In the above implementation, x is the node on which the rotation is performed and y is the right
child of the node x.

Deletion in Splay tree

As we know that splay trees are the variants of the Binary search tree, so deletion operation in
the splay tree would be similar to the BST, but the only difference is that the delete operation is
followed in splay trees by the splaying operation.

Types of Deletions:

There are two types of deletions in the splay trees:

1. Bottom-up splaying

2. Top-down splaying

Bottom-up splaying

In bottom-up splaying, first we delete the element from the tree and then we perform the
splaying on the deleted node.

Let's understand the deletion in the Splay tree.

Suppose we want to delete 12, 14 from the tree shown below:

● First, we simply perform the standard BST deletion operation to delete 12

element. As 12 is a leaf node, so we simply delete the node from the tree.

The deletion is still not completed. We need to splay the parent of the deleted node, i.e., 10. We
have to perform Splay(10) on the tree. As we can observe in the above tree that 10 is at the
right of node 7, and node 7 is at the left of node 13. So, first, we perform the left rotation on
node 7 and then we perform the right rotation on node 13, as shown below:

Prajyoti Niketan College- Pudukad Department of Computer Science

Still, node 10 is not a root node; node 10 is the left child of the root node. So, we need to
perform the right rotation on the root node, i.e., 14 to make node 10 a root node as shown
below:

● Now, we have to delete the 14 element from the tree, which is shown below:

As we know that we cannot simply delete the internal node. We will replace the value of the
node either using inorder predecessor or inorder successor. Suppose we use inorder
successor in which we replace the value with the lowest value that exist in the right subtree. The
lowest value in the right subtree of node 14 is 15, so we replace the value 14 with 15. Since
node 14 becomes the leaf node, so we can simply delete it as shown below:

Still, the deletion is not completed. We need to perform one more operation, i.e., splaying in
which we need to make the parent of the deleted node as the root node. Before deletion, the
parent of node 14 was the root node, i.e., 10, so we do need to perform any splaying in this
case.

Top-down splaying

In top-down splaying, we first perform the splaying on which the deletion is to be performed and
then delete the node from the tree. Once the element is deleted, we will perform the join
operation.

Let's understand the top-down splaying through an example.

Suppose we want to delete 16 from the tree which is shown below:

Step 1: In top-down splaying, first we perform splaying on the node 16. The node 16 has both
parent as well as grandparent. The node 16 is at the right of its parent and the parent node is also
at the right of its parent, so this is a zag zag situation. In this case, first, we will perform the left
rotation on node 13 and then 14 as shown below:

The node 16 is still not a root node, and it is a right child of the root node, so we need to perform
left rotation on the node 12 to make node 16 as a root node.

Once the node 16 becomes a root node, we will delete the node 16 and we will get two different
trees, i.e., left subtree and right subtree as shown below:

As we know that the values of the left subtree are always lesser than the values of the right
subtree. The root of the left subtree is 12 and the root of the right subtree is 17. The first step is
to find the maximum element in the left subtree. In the left subtree, the maximum element is 15,
and then we need to perform splaying operation on 15.

As we can observe in the above tree that the element 15 is having a parent as well as a
grandparent. A node is right of its parent, and the parent node is also right of its parent, so we
need to perform two left rotations to make node 15 a root node as shown below:

Prajyoti Niketan College- Pudukad Department of Computer Science

After performing two rotations on the tree, node 15 becomes the root node. As we can see, the
right child of the 15 is NULL, so we attach node 17 at the right part of the 15 as shown below,
and this operation is known as a join operation.

Note: If the element is not present in the splay tree, which is to be deleted, then
splaying would be performed. The splaying would be performed on the last
accessed element before reaching the NULL.

Algorithm of Delete operation

1. If(root==NULL)
2. return NULL
3. Splay(root, data)
4. If data!= root->data
5. Element is not present
6. If root->left==NULL
7. root=root->right
8. else
9. temp=root
10. Splay(root->left, data)
11. root1->right=root->right
12. free(temp)
13. return root

In the above algorithm, we first check whether the root is Null or not; if the root is NULL means
that the tree is empty. If the tree is not empty, we will perform the splaying operation on the
element which is to be deleted. Once the splaying operation is completed, we will compare the
root data with the element which is to be deleted; if both are not equal means that the element is
not present in the tree. If they are equal, then the following cases can occur:

Case 1: The left of the root is NULL, the right of the root becomes the root node.

Case 2: If both left and right exist, then we splay the maximum element in the left subtree. When
the splaying is completed, the maximum element becomes the root of the left subtree. The right
subtree would become the right child of the root of the left subtree.

[Link]

Prajyoti Niketan College- Pudukad Department of Computer Science

Leftist Tree / Leftist Heap

A leftist tree or leftist heap is a priority queue implemented with a variant of a

binary heap. Every node has an s-value (or rank or distance) which is the
distance to the nearest leaf. In contrast to a binary heap (Which is always a
complete binary tree), a leftist tree may be very unbalanced.

Below are time complexities of Leftist Tree / Heap.

Function Complexity Comparison

1) Get Min: O(1) [same as both Binary and Binomial]

2) Delete Min: O(Log n) [same as both Binary and Binomial]

3) Insert: O(Log n) [O(Log n) in Binary and O(1) in Binomial and O(Log n) for
worst case]

4) Merge: O(Log n) [O(Log n) in Binomial]

A leftist tree is a binary tree with properties:

1. Normal Min Heap Property : key(i) >= key(parent(i))
2. Heavier on left side : dist(right(i)) <= dist(left(i)). Here, dist(i) is the number
of edges on the shortest path from node i to a leaf node in extended binary
tree representation (In this representation, a null child is considered as
external or leaf node). The shortest path to a descendant external node is
through the right child. Every subtree is also a leftist tree and dist( i ) = 1 +
dist( right( i ) ).

Prajyoti Niketan College- Pudukad Department of Computer Science

Example: The below leftist tree is presented with its distance calculated for each
node with the procedure mentioned above. The rightmost node has a rank of 0 as
the right sub tree of this node is null and its parent has a distance of 1 by dist( i ) =
1 + dist( right( i )). The same is followed for each node and their s-value( or rank)
is calculated.

From above second property, we can draw two conclusions :

1. The path from root to rightmost leaf is the shortest path from root to a leaf.
2. If the path to rightmost leaf has x nodes, then leftist heap has atleast 2x –
1 nodes. This means the length of path to rightmost leaf is O(log n) for a
leftist heap with n nodes.

Operations :
1. The main operation is merge().
2. deleteMin() (or extractMin() can be done by removing root and calling
merge() for left and right subtrees.
3. insert() can be done be create a leftist tree with single key (key to be
inserted) and calling merge() for given tree and tree with single node.

Idea behind Merging :

Since right subtree is smaller, the idea is to merge right subtree of a tree with
other tree. Below are abstract steps.
1. Put the root with smaller value as the new root.
2. Hang its left subtree on the left.
3. Recursively merge its right subtree and the other tree.
4. Before returning from recursion:
– Update dist() of merged root.
– Swap left and right subtrees just below root, if needed, to keep leftist
property of merged result

Prajyoti Niketan College- Pudukad Department of Computer Science

Source : [Link]
[Link]

Detailed Steps for Merge:

1. Compare the roots of two heaps.
2. Push the smaller key into an empty stack, and move to the right child of
smaller key.
3. Recursively compare two keys and go on pushing the smaller key onto
the stack and move to its right child.
4. Repeat until a null node is reached.
5. Take the last node processed and make it the right child of the node at top
of the stack, and convert it to leftist heap if the properties of leftist heap are
violated.(swap left & right child)
6. Recursively go on popping the elements from the stack and making them
the right child of new stack top.

Example:

Consider two leftist heaps given below:

Merge them into a single leftist heap

The subtree at node 7 violates the property of leftist heap so we swap it with the
left child and retain the property of leftist heap.

Convert to leftist heap. Repeat the process

The worst case time complexity of this algorithm is O(log n) in the worst case,
where n is the number of nodes in the leftist heap.

Prajyoti Niketan College- Pudukad Department of Computer Science

Another example of merging two leftist heap:

To insert a node

To insert a node into a leftist heap, merge the leftist heap with the node After deleting root X from a
leftist heap, merge its left and right sub heaps In summary, there is only one operation, a merge

Height of a leftist heap ≈ O(log n) Maximum number of values stored in Stack ≈ 2 ∗

O(log n) ≈ O(log n) Total cost of merge ≈ O(log n)

Comparison of Search Trees

The comparison of search trees is performed based on the Time complexity of search, insertion and

deletion operations in search trees. The following table provides the Time complexities of search trees.

These Time complexities are defined for 'n' number of elements.

Average Case Worst Case

Search
Tree Insert Delete Search Insert Delete Search

Binary O(log n) O(log O(log O(n) O(n) O(n)

Search n) n)
Tree

AVL O(log2 O(log2 O(log2 O(log2 O(log2 O(log2

Tree n) n) n) n) n) n)

B - Tree O(log n) O(log O(log O(log O(log n) O(log n)

n) n) n)

Prajyoti Niketan College- Pudukad Department of Computer Science

 Red - O(log n) O(log O(log O(log O(log n) O(log n)
Black n) n) n)
Tree

Splay O(log2 O(log2 O(log2 O(log2 O(log2 O(log2

Tree n) n) n) n) n) n)

Skew Heap
A skew heap (or self – adjusting heap) is a heap data structure implemented as a
binary tree. Skew heaps are advantageous because of their ability to merge more
quickly than binary heaps.

In contrast with binary heaps, there are no structural constraints, so there is no

guarantee that the height of the tree is logarithmic.

Only two conditions must be satisfied :

1. The general heap order must be there (root is minimum and same is
recursively true for subtrees), but balanced property (all levels must be full
except the last) is not required.
2. Main operation in Skew Heaps is Merge. We can implement other
operations like insert, extractMin(), etc using Merge only.

Ø Skew Simplifies leftist heap by not maintaining null path lengths

Ø Skew Heaps are a self-adjusting form of Leftist Heap by
unconditionally swapping all nodes in the right merge path Skew
Heaps maintain a short right path from the root.
Ø Swapping children at every step.
Ø A Skew (min)Heap is a binary tree that satisfies the following
conditions.
If X is a node and L and R are its left and right children, then:
· 1 [Link] ≤ [Link]

· 2 [Link] ≤ [Link]

Prajyoti Niketan College- Pudukad Department of Computer Science

 Ø A Skew (max)Heap is a binary tree that satisfies the following
conditions.
If X is a node and L and R are its left and right children, then:
· 1 [Link] ≥ [Link]

· 2 [Link] ≥ [Link]

Ø Skews are binarys trees with heap property

Ø skew merging avoids right-heavy trees, gives O(log n) amortised

complexity

Ø other operations are based on merge

Example :

1. Consider the skew heap 1 to be

2. The second heap to be considered

3. And we obtain the final merged tree as

Recursive Merge Process :

merge(h1, h2)
1. Compare roots of two heaps
2. Recursively merge the heap that has the larger root with the right
subtree of the other heap.
3. Make the resulting merge the right subtree of the heap that has
smaller root.
4. Swap the children of the new heap

Alternatively, there is a non-recursive approach which tends to be a little

clearer, but does require some sorting at the outset.

Prajyoti Niketan College- Pudukad Department of Computer Science
 · Split each heap into subtrees by cutting every rightmost path. (From the
root node, sever the right node and make the right child its own subtree.)
This will result in a set of trees in which the root either only has a left child
or no children at all.
· Sort the subtrees in ascending order based on the value of the root node of
each subtree.
· While there are still multiple subtrees, iteratively recombine the last two
(from right to left).
· If the root of the second-to-last subtree has a left child, swap it to be the
right child.
· Link the root of the last subtree as the left child of the second-to-last
subtree.

Adding Values

Adding a value to a skew heap is like merging a tree with one node together with the

original tree. The root node is linked as the left child of the new value, which itself

becomes the new root.

Removing Values

Removing the first value in a heap can be accomplished by removing the root and (a)

merging the child subtrees if the root has two children, (b) replacing the root with the

non-nil child, or (c) ending with an empty heap.

Binomial Heap
As we have already discussed about the heap data structure which is of two types, i.e., min heap
and max heap. A binomial heap can be defined as the collection of binomial tree that satisfies
the heap properties, i.e., min heap. The min heap is a heap in which each node has a value lesser
than the value of its child nodes.

To understand the binomial heap, we first understand about the binomial tree.

What is Binomial tree?

Prajyoti Niketan College- Pudukad Department of Computer Science
A Binomial tree is a tree in which Bk is an ordered tree defined recursively, where k is defined as
the order of the binomial tree.

● If the binomial tree is represented as B0 then the tree consists of a single node.
● In general terms, Bk consists of two binomial trees, i.e., Bk-1 and Bk-1 are linked
together in which one tree becomes the left subtree of another binomial tree. It can
be represented as:

Let's understand through examples.

If B0, where k is 0, means that there would exist only one node in the tree shown as below:

If B1, where k is 1, means k-1 equal to 0. Therefore, there would be two binomial trees of B0 in
which one B0 becomes the left subtree of another B0.

If B2, where k is 2, means k-1 equal to 1. Therefore, there would be two binomial trees of B1 in
which one B1 becomes the left subtree of another B1.

If B3 , where k is 3, means k-1 equal to 2. Therefore, there would be two binomial trees of B3 in
which one B3 becomes the left subtree of another B3.]

Properties of Binomial tree

● There are 2k
If k=1 then 20 = 1. The number of nodes is 1.
If k = 2 then 21 = 2. The number of nodes is 2.
● The height of the tree is k.
If k=0 then the height of the tree would be 0.
If k=1 then the height of the tree would be 1.
● There are exactly kci or k/i nodes at depth i = 0, 1..k.
For example, if k is equal to 4 and at depth i=2, we have to determine the
number of nodes.

Binomial Heap

A binomial heap is a collection of binomial trees that satisfies the properties of a min- heap.

Prajyoti Niketan College- Pudukad Department of Computer Science

The following are the two properties of the binomial heap:

● Each binomial heap obeys the min-heap properties.

● For any non-negative integer k, there should be atleast one binomial tree in a heap
where root has degree k.

Let's understand the above two properties through an example.

The above figure has three binomial trees, i.e., B0, B2, B3. The above all three binomial trees
satisfy the min heap's property as all the nodes have a smaller value than the child nodes.

The above figure also satisfies the second property of the binomial heap. For example, if we
consider the value of k as 3, then we can observe in the above figure that the binomial tree of
degree 3 exists in the heap.

Representation of Binomial heap node

The above figure shows the representation of the binomial heap node in the memory. The first
block in the memory contains the pointer that stores the address of the parent of the node.

The second block stores the key value of the node.

The third block contains the degree of the node.

The fourth block is divided into two parts, i.e., left child and sibling. The left child contains the
address of the left child of a node, whereas the sibling contains the address of the sibling.

Important point

● If we want to create the binomial heap of 'n' nodes, that can be simply defined by
the binary number of 'n'. For example: if we want to create the binomial heap of 13
nodes; the binary form of 13 is 1101, so if we start the numbering from the
rightmost digit, then we can observe that 1 is available at the 0, 2, and 3 positions;
therefore, the binomial heap with 13 nodes will have B0, B2, and B3 binomial trees.

Let's consider another example.

If we want to create the binomial heap of 9 nodes. The binary form of 9 is 1001. As we can observe
in the binary number that 1 digit is available at 0 and 3 position; therefore, the binomial heap will
contain the binomial trees of 0 and 3 degree.

Operations on Binomial Heap

Prajyoti Niketan College- Pudukad Department of Computer Science
 ● Creating a new binomial heap: When we create a new binomial heap then it
simply takes O(1) time because creating a heap will create the head of the heap
in which no elements are attached.
● Finding the minimum key: As we know that binomial heap is a collection of
binomial trees and each binomial tree satisfies the property of min heap means
root node contains the minimum value. Therefore, we need to compare only root
node of all the binomial trees to find the minimum key. The time complexity for
finding a minimum key is O(logn).
● Union of two binomial heap: If we want to combine two binomial heaps, then
we can simply find the union of two binomial heaps. The time complexity for
finding a union is O(logn).
● Inserting a node: The time complexity for inserting a node is O(logn).
● Extracting minimum key: The time complexity for removing a minimum key is
O(logn).
● Decreasing a key: When the key value of any node is changed, then the
binomial tree does not satisfy the min-heap. We need to perform some
rearrangements in order to satisfy the min-heap property. The time complexity
would be O(logn).
● Deleting a node: The time complexity for deleting a node is O(logn).

Union of two Binomial Heap

To perform the union to two binomial heap, we will use the following cases:

Case 1: If degree[x] is not equal to degree[next x] then move pointer ahead.

Case 2: if degree[x] = degree[next x] = degree[sibling(next x)] then

Move pointer ahead.

Case 3: If degree[x] = degree[next x] but not equal to degree[sibling[next x]]

and key[x] < key[next x] then remove [next x] from root and attached to x.

Prajyoti Niketan College- Pudukad Department of Computer Science

Case 4: If degree[x] = degree[next x] but not equal to degree[sibling[next x]]

and key[x] > key[next x] then remove x from root and attached to [next x].

Let's understand the union of two binomial heaps through an example.

As we can observe in the above figure that there are two binomial heaps. First, we combine
these two binomial heaps. To combine these two binomial heaps, we need to arrange them in
the increasing order of binomial trees shown as below:

● Initially, x points to the B0 having value 12, and next[x] points to B0 having value
18. The B1 is the sibling of B0 having node value 18. Therefore, the sibling B 1 is
represented as sibling[next x]. Now, we will apply case 1. Case 1 says that 'if
degree[x] is not equal to degree[next x] then move pointer ahead' but in the
above example, the degree of x is the same as the degree of next x, so this case
is not valid.

Now we will apply case 2. The case 2 says that 'if degree[x] = degree[next x] =
degree[sibling(next x)] then Move pointer ahead'. In the above example, the degree of x is
same as the degree of the next x but not equal to the degree of a sibling of next x; therefore, this
case is not valid.

Now we will apply case 3. The case 3 says that 'If degree[x] = degree[next x] but not equal to
degree[sibling[next x] and key[x] < key[next x] then remove [next x] from root and attached
to x'. In the above example, the degree of x is equal to the degree of next x but equal to the
degree of a sibling of next x, and the key value of x, i.e., 12, is less than the value of next x, i.e.,
18; therefore, this case is valid. So, we have to remove the next x, i.e., 18, from the root and
attach it to the x, i.e., 12, shown as below:

As we can observe in the above binomial heap that node 18 is attached to the node 12.

● Now we will reapply the cases in the above binomial heap. First, we will apply case
1. Since x is pointing to node 12 and next x is pointing to node 7, the degree of x
is equal to the degree of next x; therefore, case 1 is not valid.

Now we will apply case 2. Since the degree of x is equal to the degree of next x and also equal
to the degree of sibling of next x; therefore, this case is valid. We will move the pointer ahead
shown as below:

Prajyoti Niketan College- Pudukad Department of Computer Science

As we can observe in the above figure that 'x' points to the binomial tree having root node 7,
next(x) points to the binomial tree having root node 3 while prev(x) points to the binomial tree
having root node 12. The sibling(next(x)) points to the binomial tree having root node 15.

● Now we will apply case 3 in the above tree. Since the degree of x is equal to the
degree of next x, i.e., 1 but not equal to the degree of a sibling of next x, i.e., 2.
Either case 3 or case 4 is valid based on the second condition. The key value of
x, i.e., 7 is greater than the key value of next(x), i.e., 3; therefore, we can say that
case 4 is valid. Here, we need to remove the x and attach it to the next(x) shown
as below:

As we can observe in the above figure that x becomes the left child of next(x). The pointer also
gets updated. Now, x will point to the binomial tree having root node 3, and degree is also changed
to 2. The next(x) points to the binomial tree having root node as 15, and the sibling(next(x)) will
point to the binomial tree having root node as 6.

● In the above tree, the degree of x, i.e., B2, is the same as the degree of next(x),
i.e., B2, but not equal to the degree of sibling(next(x)), i.e., B 4. Therefore, either
case 3 or case 4 is valid based on the second condition. Since the key value of x
is less than the value of next(x) so we need to remove next(x) and attach it to the
x shown as below:

As we can observe in the above figure that next(x) becomes the left child of x, and the degree of
x also gets changed to B3. The pointer next(x) also gets updated, and it now points to the binomial
tree having root node 6. The degree of x is 3, and the degree of next(x) is 4. Since the degrees
of x and next(x) are not equal, so case 1 is valid. We will move the pointer ahead, and now x
points to node 6.

The B4 is the last binomial tree in a heap, so it leads to the termination of the loop. The above tree
is the final tree after the union of two binomial heaps.

Inserting a new node in a Binomial heap

Now we will see how to insert a new node in a heap. Consider the below heap, and we want to
insert a node 15 in a heap.

Prajyoti Niketan College- Pudukad Department of Computer Science

In the above heap, there are three binomial trees of degree B0, B1, and B2, where B0 is attached
to the head of the heap.

Let's assume that node 15 is attached to the head of the heap shown as below:

First, we will combine these two heaps. As the degree of node 12 and node 15 is B0 so node 15
is attached to the node 12 shown in the above figure.

Now we assign 'x' to the B0 having key value 12, next(x) to the B0 having key value 15, and
sibling(next(x)) to the B1 having key value 7.

Since the degree of x is equal to the degree of next(x) but not equal to the degree of sibling of
next(x) so either case 3 or case 4 will be applied to the heap. The key value of x is greater than
the key value of next(x); therefore, next(x) would be removed and attached it to the x.

Now, we will reapply the cases in the above heap. Now, x points to the node 12 having degree
B1, next(x) points to the node 7 having degree B1 and sibling(next(x)) points to the node 15
having degree B2. Since the degree of x is same as the degree of next(x) but not equal to the
degree of sibling of next(x), so either case 3 or case 4 is applied. The key value of x is greater
than the key value of next(x); therefore, the x is removed and attached to the x shown as below:

As we can observe in the above figure that when 'x' is attached to the next(x) then the degree of
node 7 is changed to B2. The pointers are also get updated. Now 'x' points to the node 7 and
next(x) points to the node 15. Now we will reapply the cases in the above heap. Since the
degree of x is equal to the degree of next(x) and the key value of x is less than the key value of
next(x); therefore, next(x) would be removed from the heap and attached it to the x shown as
below:

As we can observe in the above heap that the degree of x gets changed to 3, and this is the
final binomial heap after inserting the node 15.

Extracting a minimum key

Here extracting a minimum key means that we need to remove the element which has minimum
key value. We already know that in min heap, the root element contains the minimum key value.
Therefore, we have to compare the key value of root node of all the binomial trees.

Consider the binomial heap which is given below:

In the above heap, the key values of root node of all the binomial trees are 12, 7 and 15. The
key value 7 is the minimum value so we will remove the node 7 from the tree shown as below:

As we can observe in the above binomial heap that the degree of node 12 is B0, degree of node
25 is B0, and degree of node 15 is B2. The pointer x points to the node 12, next(x) points to the
node 25, and sibling(next(x)) points to the node 15. Since the degree of x is equal to the degree
Prajyoti Niketan College- Pudukad Department of Computer Science
of next(x) but not equal to the degree of sibling(next(x)); therefore, either case 3 or case 4 will be
applied to the above heap. The key value of x is less than the key value of next(x), so node 25
will be removed and attached to the node 12 shown as below:

The degree of node 12 is also changed to 1.

Decreasing a key

Now we will see how to decrease a key with the help of an example. Consider the below heap,
and we will decrease the key 45 by 7:

After decreasing the key by 7, the heap would look like:

Since the above heap does not satisfy the min-heap property, element 7 will be compared with
an element 30; since the element 7 is less than the element 30 so 7 will be swapped with 30
element shown as below:

Now we will again compare element 7 with its root element, i.e., 8. Since element 7 is less than
element 8 so element 7 will be swapped with an element 8 shown as below:

Now, the above heap satisfies the property of the min-heap.

Deleting a node

Now we will see how to delete a node with the help of an example. Consider the below heap,
and we want to delete node 41:

First, we replace node 41 with the smallest value, and the smallest value is -infinity, shown as
below:

Now we will swap the -infinity with the root node of the tree shown as below:

The next step is to extract the minimum key. Since the minimum key in a heap is -infinity so we
will extract this key, and the heap would be:

Fibonacci Heaps

Like Binomial heaps, Fibonacci heaps are collection of trees. They are loosely based on binomial
heaps. Unlike trees with in binomial heaps are ordered trees within Fibonacci heaps are rooted
but unordered.

Each node x in Fibonacci heaps contains a pointer p[x] to its parent, and a pointer child[x] to any
one of its children. The children of x are linked together in a circular doubly linked list known as
child list of x. Each child y in a child list has pointers left[y] and right[y] to point left and right siblings

Prajyoti Niketan College- Pudukad Department of Computer Science

of y respectively. If node y is only child then left[y] = right[y] = y. The order in which sibling appears
in a child list is arbitrary.

Example of Fibonacci Heap

This Fibonacci Heap H consists of five Fibonacci Heaps and 16 nodes. The line with arrow head
indicates the root list. Minimum node in the list is denoted by min[H] which is holding 4.

The asymptotically fast algorithms for problems such as computing minimum spanning trees,
finding single source of shortest paths etc. makes essential use of Fibonacci heaps.

In terms of Time Complexity, Fibonacci Heap beats both Binary and Binomial
Heaps.
Below are amortized time complexities of Fibonacci Heap.

1) Find Min: Θ(1) [Same as both Binary and Binomial]

2) Delete Min: O(Log n) [Θ(Log n) in both Binary and Binomial]
3) Insert: Θ(1) [Θ(Log n) in Binary and Θ(1) in Binomial]
4) Decrease-Key: Θ(1) [Θ(Log n) in both Binary and Binomial]
5) Merge: Θ(1) [Θ(m Log n) or Θ(m+n) in Binary and Θ(Log n) in Binomial]

Like Binomial Heap, Fibonacci Heap is a collection of trees with min-heap or

max-heap property. In Fibonacci Heap, trees can can have any shape even all
trees can be single nodes (This is unlike Binomial Heap where every tree has to
be Binomial Tree).
Below is an example Fibonacci Heap taken from here.
Fibonacci Heap maintains a pointer to minimum value (which is root of a tree). All
tree roots are connected using circular doubly linked list, so all of them can be
accessed using single ‘min’ pointer.
The main idea is to execute operations in “lazy” way. For example merge
operation simply links two heaps, insert operation simply adds a new tree with
single node. The operation extract minimum is the most complicated operation. It
does delayed work of consolidating trees. This makes delete also complicated as
delete first decreases key to minus infinite, then calls extract minimum.

Below are some interesting facts about Fibonacci Heap

1. The reduced time complexity of Decrease-Key has importance in Dijkstra
and Prim algorithms. With Binary Heap, time complexity of these
algorithms is O(VLogV + ELogV). If Fibonacci Heap is used, then time
complexity is improved to O(VLogV + E)
Prajyoti Niketan College- Pudukad Department of Computer Science
 2. Although Fibonacci Heap looks promising time complexity wise, it has
been found slow in practice as hidden constants are high
3. Fibonacci heap are mainly called so because Fibonacci numbers are used
in the running time analysis. Also, every node in Fibonacci Heap has
degree at most O(log n) and the size of a subtree rooted in a node of
degree k is at least Fk+2, where Fk is the kth Fibonacci number.

Fibonacci Heap – Insertion and Union

Fibonacci Heap is a collection of trees with min-heap or max-heap property. In

Fibonacci Heap, trees can have any shape even all trees can be single nodes (This
is unlike Binomial Heap where every tree has to be Binomial Tree).

In this article, we will discuss Insertion and Union operation on Fibonacci Heap.

Insertion: To insert a node in a Fibonacci heap H, the following algorithm is

followed:
1. Create a new node ‘x’.
2. Check whether heap H is empty or not.
3. If H is empty then:
· Make x as the only node in the root list.
· Set H(min) pointer to x.
4. Else:

· Insert x into root list and update H(min).

Union: Union of two Fibonacci heaps H1 and H2 can be accomplished as

follows:
1. Join root lists of Fibonacci heaps H1 and H2 and make a single Fibonacci
heap H.
2. If H1(min) < H2(min) then:
· H(min) = H1(min).
3. Else:

· H(min) = H2(min).

Prajyoti Niketan College- Pudukad Department of Computer Science