Heaps
Heaps
Heaps
5 Binary Heap 18
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6 Binomial Heap 20
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1
Contents
18 HeapSort 89
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
3
Contents
54 Overview of Data Structures | Set 2 (Binary Tree, BST, Heap and Hash)289
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
55 Print all elements in sorted order from row and column wise sorted
matrix 293
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
62 Rearrange characters in a string such that no two adjacent are same 318
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
4
Contents
68 Sum of all elements between k1’th and k2’th smallest elements 348
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
72 Why is Binary Heap Preferred over BST for Priority Queue? 361
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
73 heapq in Python to print all elements in sorted order from row and
column wise sorted matrix 363
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
5
Chapter 1
Adding elements of an array until every element becomes greater than or equal to k - Geeks-
forGeeks
We are given a list of N unsorted elements, we need to find minimum number of steps in
which the elements of the list can be added to make all the elements greater than or equal
to K. We are allowed to add two elements together and make them one.
Examples:
Input : arr[] = {1 10 12 9 2 3}
K = 6
Output : 2
First we add (1 + 2), now the new list becomes
3 10 12 9 3, then we add (3 + 3), now the new
list becomes 6 10 12 9, Now all the elements in
the list are greater than 6. Hence the output is
2 i:e 2 operations are required
to do this.
As we can see from above explanation, we need to extract two smallest elements and then
add their sum to list. We need to continue this step until all elements are greater than or
equal to K.
Method 1 (Brute Force):
We can create a simple array the sort it and then add two minimum elements and keep on
storing them back in the array until all the elements become greater than K.
6
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
Method 2 (Efficient):
If we take a closer look, we can notice that this problem is similar to Huffman coding. We
use Min Heap as the main operations here are extract min and insert. Both of these
operations can be done in O(Log n) time.
C++
int parent(int i)
{
return (i-1)/2;
}
7
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
int getSize()
{
return heap_size;
}
8
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
}
}
return root;
}
9
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
res++;
}
return res;
}
// Driver code
int main()
{
int arr[] = {1, 10, 12, 9, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 6;
cout << countMinOps(arr, n, k);
return 0;
}
Java
10
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
11
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
return root;
}
int getSize()
{
return heap_size;
}
12
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
heap_size++;
int i = heap_size - 1;
harr[i] = k;
int res = 0;
res++;
}
return res;
}
// Driver code
public static void main(String args[])
{
int arr[] = {1, 10, 12, 9, 2, 3};
int n = arr.length;
13
Chapter 1. Adding elements of an array until every element becomes greater than or equal
to k
int k = 6;
System.out.println(countMinOps(arr, n, k));
}
}
// This code is contributed by Sumit Ghosh
Output:
Source
https://www.geeksforgeeks.org/adding-elements-array-every-element-becomes-greater-k/
14
Chapter 2
Source
https://www.geeksforgeeks.org/applications-of-heap-data-structure/
15
Chapter 3
Source
https://www.geeksforgeeks.org/applications-priority-queue/
16
Chapter 4
Source
https://www.geeksforgeeks.org/array-representation-of-binary-heap/
17
Chapter 5
Binary Heap
10 10
/ \ / \
20 100 15 30
/ / \ / \
30 40 50 100 40
18
Chapter 5. Binary Heap
2 4 1
Source
https://www.geeksforgeeks.org/binary-heap/
19
Chapter 6
Binomial Heap
20
Chapter 6. Binomial Heap
21
Chapter 6. Binomial Heap
Binomial Heap:
A Binomial Heap is a set of Binomial Trees where each Binomial Tree follows Min Heap
property. And there can be at most one Binomial Tree of any degree.
Examples Binomial Heap:
12------------10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
A Binomial Heap with 13 nodes. It is a collection of 3
Binomial Trees of orders 0, 2 and 3 from left to right.
10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
22
Chapter 6. Binomial Heap
4) delete(H): Like Binary Heap, delete operation first reduces the key to minus infinite, then
calls extractMin().
5) decreaseKey(H): decreaseKey() is also similar to Binary Heap. We compare the decreases
key with it parent and if parent’s key is more, we swap keys and recur for the parent. We
stop when we either reach a node whose parent has a smaller key or we hit the root node.
Time complexity of decreaseKey() is O(Logn).
Union operation in Binomial Heap:
Given two Binomial Heaps H1 and H2, union(H1, H2) creates a single Binomial Heap.
1) The first step is to simply merge the two Heaps in non-decreasing order of degrees. In
the following diagram, figure(b) shows the result after merging.
2) After the simple merge, we need to make sure that there is at most one Binomial Tree of
any order. To do this, we need to combine Binomial Trees of the same order. We traverse
the list of merged roots, we keep track of three-pointers, prev, x and next-x. There can be
following 4 cases when we traverse the list of roots.
—–Case 1: Orders of x and next-x are not same, we simply move ahead.
In following 3 cases orders of x and next-x are same.
—–Case 2: If the order of next-next-x is also same, move ahead.
—–Case 3: If the key of x is smaller than or equal to the key of next-x, then make next-x as
a child of x by linking it with x.
—–Case 4: If the key of x is greater, then make x as the child of next.
The following diagram is taken from 2nd Edition of CLRS book.
23
Chapter 6. Binomial Heap
24
Chapter 6. Binomial Heap
in and extractMin() and delete()). The idea is to represent Binomial Trees as the leftmost
child and right-sibling representation, i.e., every node stores two pointers, one to the leftmost
child and other to the right sibling.
Sources:
Introduction to Algorithms by Clifford Stein, Thomas H. Cormen, Charles E. Leiserson,
Ronald L.
This article is contributed by Shivam. Please write comments if you find anything incorrect,
or you want to share more information about the topic discussed above
Source
https://www.geeksforgeeks.org/binomial-heap-2/
25
Chapter 7
1. It should be a complete tree (i.e. all levels except last should be full).
2. Every node’s value should be greater than or equal to its child node (considering
max-heap).
26
Chapter 7. Check if a given Binary Tree is Heap
We check each of the above condition separately, for checking completeness isComplete and
for checking heap isHeapUtil function are written.
Detail about isComplete function can be found here.
isHeapUtil function is written considering following things –
1. Every Node can have 2 children, 0 child (last level nodes) or 1 child (there can be at
most one such node).
2. If Node has No child then it’s a leaf node and return true (Base case)
3. If Node has one child (it must be left child because it is a complete tree) then we need
to compare this node with its single child only.
4. If Node has both child then check heap property at Node at recur for both subtrees.
Complete code.
Implementation
C/C++
27
Chapter 7. Check if a given Binary Tree is Heap
28
Chapter 7. Check if a given Binary Tree is Heap
else
{
// Check heap property at Node and
// Recursive check heap property at left and right subtree
if (root->key >= root->left->key &&
root->key >= root->right->key)
return ((isHeapUtil(root->left)) &&
(isHeapUtil(root->right)));
else
return (false);
}
}
// Driver program
int main()
{
struct Node* root = NULL;
root = newNode(10);
root->left = newNode(9);
root->right = newNode(8);
root->left->left = newNode(7);
root->left->right = newNode(6);
root->right->left = newNode(5);
root->right->right = newNode(4);
root->left->left->left = newNode(3);
root->left->left->right = newNode(2);
root->left->right->left = newNode(1);
if (isHeap(root))
printf("Given binary tree is a Heap\n");
else
printf("Given binary tree is not a Heap\n");
return 0;
}
29
Chapter 7. Check if a given Binary Tree is Heap
Java
Node(int k)
{
key = k;
left = right = null;
}
}
class Is_BinaryTree_MaxHeap
{
/* This function counts the number of nodes in a binary tree */
int countNodes(Node root)
{
if(root==null)
return 0;
return(1 + countNodes(root.left) + countNodes(root.right));
}
30
Chapter 7. Check if a given Binary Tree is Heap
31
Chapter 7. Check if a given Binary Tree is Heap
if(bt.isHeap(root) == true)
System.out.println("Given binary tree is a Heap");
else
System.out.println("Given binary tree is not a Heap");
}
}
Python
if root.right is None:
return root.key >= root.left.key
else:
if (root.key >= root.left.key and
root.key >= root.right.key):
return (self.heap_propert_util(root.left) and
self.heap_propert_util(root.right))
else:
return False
32
Chapter 7. Check if a given Binary Tree is Heap
if root is None:
return True
if index >= node_count:
return False
return (self.complete_tree_util(root.left, 2 *
index + 1, node_count) and
self.complete_tree_util(root.right, 2 *
index + 2, node_count))
def check_if_heap(self):
node_count = self.count_nodes(self)
if (self.complete_tree_util(self, 0, node_count) and
self.heap_propert_util(self)):
return True
else:
return False
# Driver Code
root = GFG(5)
root.left = GFG(2)
root.right = GFG(3)
root.left.left = GFG(1)
if root.check_if_heap():
print("Given binary tree is a heap")
else:
print("Given binary tree is not a Heap")
Output:
This article is contributed by Utkarsh Trivedi. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Improved By : scorncer17
Source
https://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-heap/
33
Chapter 8
If we observe the above problem closely, we can notice that the lengths of the ropes which
are picked first are included more than once in total cost. Therefore, the idea is to connect
smallest two ropes first and recur for remaining ropes. This approach is similar to Huffman
Coding. We put smallest ropes down the tree so that they can be repeated multiple times
rather than the longer ropes.
Following is complete algorithm for finding the minimum cost for connecting n ropes.
Let there be n ropes of lengths stored in an array len[0..n-1]
1) Create a min heap and insert all lengths into the min heap.
2) Do following while number of elements in min heap is not one.
……a) Extract the minimum and second minimum from min heap
……b) Add the above two extracted values and insert the added value to the min-heap.
……c) Maintain a variable for total cost and keep incrementing it by the sum of extracted
34
Chapter 8. Connect n ropes with minimum cost
values.
3) Return the value of this total cost.
Following is C++ implementation of above algorithm.
35
Chapter 8. Connect n ropes with minimum cost
smallest = right;
if (smallest != idx)
{
swapMinHeapNode(&minHeap->harr[smallest], &minHeap->harr[idx]);
minHeapify(minHeap, smallest);
}
}
// Creates a min heap of capacity equal to size and inserts all values
36
Chapter 8. Connect n ropes with minimum cost
// The main function that returns the minimum cost to connect n ropes of
// lengths stored in len[0..n-1]
int minCost(int len[], int n)
{
int cost = 0; // Initialize result
Output:
37
Chapter 8. Connect n ropes with minimum cost
Time Complexity: Time complexity of the algorithm is O(nLogn) assuming that we use a
O(nLogn) sorting algorithm. Note that heap operations like insert and extract take O(Logn)
time.
Algorithmic Paradigm: Greedy Algorithm
A simple implementation with STL in C++
Following is a simple implementation that uses priority_queue available in STL. Thanks to
Pango89 for providing below code.
C++
#include<iostream>
#include<queue>
// Initialize result
int res = 0;
return res;
}
38
Chapter 8. Connect n ropes with minimum cost
int main()
{
int len[] = {4, 3, 2, 6};
int size = sizeof(len)/sizeof(len[0]);
cout << "Total cost for connecting ropes is " << minCost(len, size);
return 0;
}
Java
class ConnectRopes
{
static int minCost(int arr[], int n)
{
// Create a priority queue
PriorityQueue<Integer> pq =
new PriorityQueue<Integer>();
// Initialize result
int res = 0;
return res;
}
39
Chapter 8. Connect n ropes with minimum cost
}
}
// This code is contributed by yash_pec
Output:
This article is compiled by Abhishek. Please write comments if you find anything incorrect,
or you want to share more information about the topic discussed above
Improved By : JAGRITIBANSAL, AbhijeetSrivastava
Source
https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/
40
Chapter 9
Input : 4
/ \
2 6
/ \ / \
1 3 5 7
Output : 7
/ \
3 6
/ \ / \
1 2 4 5
The given BST has been transformed into a
Max Heap.
All the nodes in the Max Heap satisfies the given
condition, that is, values in the left subtree of
a node should be less than the values in the right
subtree of the node.
41
Chapter 9. Convert BST to Max Heap
2. Perform the inorder traversal of the BST and copy the node values in the arr[] in sorted
order.
3. Now perform the postorder traversal of the tree.
4. While traversing the root during the postorder traversal, one by one copy the values from
the array arr[] to the nodes.
struct Node {
int data;
Node *left, *right;
};
42
Chapter 9. Convert BST to Max Heap
43
Chapter 9. Convert BST to Max Heap
// Driver Code
int main()
{
// BST formation
struct Node* root = getNode(4);
root->left = getNode(2);
root->right = getNode(6);
root->left->left = getNode(1);
root->left->right = getNode(3);
root->right->left = getNode(5);
root->right->right = getNode(7);
convertToMaxHeapUtil(root);
cout << "Postorder Traversal of Tree:" << endl;
postorderTraversal(root);
return 0;
}
Output:
Source
https://www.geeksforgeeks.org/convert-bst-to-max-heap/
44
Chapter 10
Input : 4
/ \
2 6
/ \ / \
1 3 5 7
Output : 1
/ \
2 5
/ \ / \
3 4 6 7
1. Create an array arr[] of size n, where n is the number of nodes in the given BST.
2. Perform the inorder traversal of the BST and copy the node values in the arr[] in
sorted order.
45
Chapter 10. Convert BST to Min Heap
46
Chapter 10. Convert BST to Min Heap
47
Chapter 10. Convert BST to Min Heap
preorderTraversal(root->right);
}
convertToMinHeapUtil(root);
cout << "Preorder Traversal:" << endl;
preorderTraversal(root);
return 0;
}
Output:
Preorder Traversal:
1 2 3 4 5 6 7
Source
https://www.geeksforgeeks.org/convert-bst-min-heap/
48
Chapter 11
Input: arr[] = [3 5 9 6 8 20 10 12 18 9]
3
/ \
5 9
/ \ / \
6 8 20 10
/ \ /
12 18 9
20
/ \
18 10
/ \ / \
12 9 9 3
/ \ /
5 6 8
The problem might look complex at first look. But our final goal is to only build the
max heap. The idea is very simple – we simply build Max Heap without caring about the
input. We start from bottom-most and rightmost internal mode of min Heap and heapify
all internal modes in bottom up way to build the Max heap.
Below is its implementation
49
Chapter 11. Convert min Heap to max Heap
C++
50
Chapter 11. Convert min Heap to max Heap
convertMaxHeap(arr, n);
return 0;
}
Java
class GFG
{
// To heapify a subtree with root at given index
static void MaxHeapify(int arr[], int i, int n)
{
int l = 2*i + 1;
int r = 2*i + 2;
int largest = i;
if (l < n && arr[l] > arr[i])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
// swap arr[i] and arr[largest]
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr, largest, n);
}
}
51
Chapter 11. Convert min Heap to max Heap
// of given size
static void printArray(int arr[], int size)
{
for (int i = 0; i < size; ++i)
System.out.print(arr[i]+" ");
}
// driver program
public static void main (String[] args)
{
// array representing Min Heap
int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
int n = arr.length;
convertMaxHeap(arr, n);
C#
// C# program to convert
// min Heap to max Heap
using System;
class GFG
{
// To heapify a subtree with
// root at given index
static void MaxHeapify(int []arr,
int i, int n)
{
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = i;
if (l < n && arr[l] > arr[i])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
52
Chapter 11. Convert min Heap to max Heap
// Driver Code
public static void Main ()
{
// array representing Min Heap
int []arr = {3, 5, 9, 6, 8,
20, 10, 12, 18, 9};
int n = arr.Length;
convertMaxHeap(arr, n);
53
Chapter 11. Convert min Heap to max Heap
Output :
The complexity of above solution might looks like O(nLogn) but it is O(n). Refer this
G-Fact for more details.
Improved By : nitin mittal
Source
https://www.geeksforgeeks.org/convert-min-heap-to-max-heap/
54
Chapter 12
A simple solution is to maintain a sorted array where smallest element is at first position
and largest element is at last. The time complexity of findMin(), findMAx() and deleteMax()
is O(1). But time complexities of deleteMin(), insert() and delete() will be O(n).
Can we do the most frequent two operations in O(1) and other operations in
O(Logn) time?.
55
Chapter 12. Design an efficient data structure for given operations
The idea is to use two binary heaps (one max and one min heap). The main challenge is,
while deleting an item, we need to delete from both min-heap and max-heap. So, we need
some kind of mutual data structure. In the following design, we have used doubly linked list
as a mutual data structure. The doubly linked list contains all input items and indexes of
corresponding min and max heap nodes. The nodes of min and max heaps store addresses
of nodes of doubly linked list. The root node of min heap stores the address of minimum
item in doubly linked list. Similarly, root of max heap stores address of maximum item in
doubly linked list. Following are the details of operations.
1) findMax(): We get the address of maximum value node from root of Max Heap. So
this is a O(1) operation.
1) findMin(): We get the address of minimum value node from root of Min Heap. So this
is a O(1) operation.
3) deleteMin(): We get the address of minimum value node from root of Min Heap. We
use this address to find the node in doubly linked list. From the doubly linked list, we get
node of Max Heap. We delete node from all three. We can delete a node from doubly linked
list in O(1) time. delete() operations for max and min heaps take O(Logn) time.
4) deleteMax(): is similar to deleteMin()
5) Insert() We always insert at the beginning of linked list in O(1) time. Inserting the
address in Max and Min Heaps take O(Logn) time. So overall complexity is O(Logn)
6) Delete() We first search the item in Linked List. Once the item is found in O(n) time,
we delete it from linked list. Then using the indexes stored in linked list, we delete it from
Min Heap and Max Heaps in O(Logn) time. So overall complexity of this operation is
O(n). The Delete operation can be optimized to O(Logn) by using a balanced binary search
tree instead of doubly linked list as a mutual data structure. Use of balanced binary search
will not effect time complexity of other operations as it will act as a mutual data structure
like doubly Linked List.
56
Chapter 12. Design an efficient data structure for given operations
57
Chapter 12. Design an efficient data structure for given operations
int size;
int capacity;
struct LNode* *array;
};
58
Chapter 12. Design an efficient data structure for given operations
59
Chapter 12. Design an efficient data structure for given operations
if ( minHeap->array[left] &&
left < minHeap->size &&
minHeap->array[left]->data < minHeap->array[smallest]->data
)
smallest = left;
if ( minHeap->array[right] &&
right < minHeap->size &&
minHeap->array[right]->data < minHeap->array[smallest]->data
)
smallest = right;
if (smallest != index)
{
// First swap indexes inside the List using address
// of List nodes
swapData(&(minHeap->array[smallest]->minHeapIndex),
&(minHeap->array[index]->minHeapIndex));
60
Chapter 12. Design an efficient data structure for given operations
if ( maxHeap->array[left] &&
left < maxHeap->size &&
maxHeap->array[left]->data > maxHeap->array[largest]->data
)
largest = left;
if ( maxHeap->array[right] &&
right < maxHeap->size &&
maxHeap->array[right]->data > maxHeap->array[largest]->data
)
largest = right;
if (largest != index)
{
// First swap indexes inside the List using address
// of List nodes
swapData(&maxHeap->array[largest]->maxHeapIndex,
&maxHeap->array[index]->maxHeapIndex);
++minHeap->size;
int i = minHeap->size - 1;
while (i && temp->data < minHeap->array[(i - 1) / 2]->data )
{
minHeap->array[i] = minHeap->array[(i - 1) / 2];
minHeap->array[i]->minHeapIndex = i;
i = (i - 1) / 2;
61
Chapter 12. Design an efficient data structure for given operations
minHeap->array[i] = temp;
minHeap->array[i]->minHeapIndex = i;
}
++maxHeap->size;
int i = maxHeap->size - 1;
while (i && temp->data > maxHeap->array[(i - 1) / 2]->data )
{
maxHeap->array[i] = maxHeap->array[(i - 1) / 2];
maxHeap->array[i]->maxHeapIndex = i;
i = (i - 1) / 2;
}
maxHeap->array[i] = temp;
maxHeap->array[i]->maxHeapIndex = i;
}
return myDS->minHeap->array[0]->data;
}
return myDS->maxHeap->array[0]->data;
}
62
Chapter 12. Design an efficient data structure for given operations
list->head = NULL;
if (isMaxHeapEmpty(maxHeap))
return;
struct LNode* temp = maxHeap->array[0];
63
Chapter 12. Design an efficient data structure for given operations
{
MinHeap *minHeap = myDS->minHeap;
MaxHeap *maxHeap = myDS->maxHeap;
if (isMinHeapEmpty(minHeap))
return;
struct LNode* temp = minHeap->array[0];
else
{
temp->next = list->head;
list->head->prev = temp;
list->head = temp;
}
}
if (isListEmpty(myDS->list))
return;
64
Chapter 12. Design an efficient data structure for given operations
65
Chapter 12. Design an efficient data structure for given operations
Insert(myDS, 40);
Insert(myDS, 5);*/
// Test Case #2
Insert(myDS, 10);
Insert(myDS, 20);
Insert(myDS, 30);
Insert(myDS, 40);
Insert(myDS, 50);
deleteMax(myDS); // 50 is deleted
printf("After deleteMax()\n");
printf("Maximum = %d \n", findMax(myDS));
printf("Minimum = %d \n\n", findMin(myDS));
deleteMin(myDS); // 10 is deleted
printf("After deleteMin()\n");
printf("Maximum = %d \n", findMax(myDS));
printf("Minimum = %d \n\n", findMin(myDS));
return 0;
}
Output:
Maximum = 50
Minimum = 10
After deleteMax()
Maximum = 40
Minimum = 10
After deleteMin()
Maximum = 40
Minimum = 20
After Delete()
Maximum = 30
Minimum = 20
66
Chapter 12. Design an efficient data structure for given operations
This article is compiled by Aashish Barnwal and reviewed by GeeksforGeeks team. Please
write comments if you find anything incorrect, or you want to share more information about
the topic discussed above
Source
https://www.geeksforgeeks.org/a-data-structure-question/
67
Chapter 13
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.
68
Chapter 13. Fibonacci Heap | Set 1 (Introduction)
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)
2. Although Fibonacci Heap looks promising time complexity wise, it has been found
slow in practice as hidden constants are high (Source Wiki).
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.
Source
https://www.geeksforgeeks.org/fibonacci-heap-set-1-introduction/
69
Chapter 14
70
Chapter 14. Find k numbers with most occurrences in the given array
71
Chapter 14. Find k numbers with most occurrences in the given array
Output:
Time Complexity: O(dlogd), where d is the count of distinct elements in the array.
Auxiliary Space: O(d), where d is the count of distinct elements in the array.
Method 2: Create the array freq_arr[] as described in Method 1 of this post. Now,
build the max heap using elements of this freq_arr[]. The root of the max heap should
be the most frequent number and in case of conflicts the larger number gets the preference.
Now remove the top k numbers of this max heap. C++ STL priority_queue has been used
as max heap.
72
Chapter 14. Find k numbers with most occurrences in the given array
Output:
Time Complexity: O(klogd), where d is the count of distinct elements in the array.
Auxiliary Space: O(d), where d is the count of distinct elements in the array.
References: https://www.careercup.com/question?id=5082885552865280
Source
https://www.geeksforgeeks.org/find-k-numbers-occurrences-given-array/
73
Chapter 15
Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap - GeeksforGeeks
Given the level order traversal of a Complete Binary Tree, determine whether the Binary
Tree is a valid Min-Heap
Examples:
74
Chapter 15. Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap
/
67
We observe that at level 0, 30 > 22, and hence
min-heap property is not satisfied
We need to check whether each non-leaf node (parent) satisfies the heap property. For this,
we check whether each parent (at index i) is smaller than its children (at indices 2*i+1 and
2*i+2, if the parent has two children). If only one child, we only check the parent against
index 2*i+1.
C++
if (2*i + 2 < n)
{
// If parent is greater than right child
if (level[i] > level[2 * i + 2])
return false;
}
}
return true;
}
// Driver code
int main()
{
int level[] = {10, 15, 14, 25, 30};
int n = sizeof(level)/sizeof(level[0]);
if (isMinHeap(level, n))
cout << "True";
else
75
Chapter 15. Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap
Java
if (2*i + 2 < n)
{
// If parent is greater than right child
if (level[i] > level[2 * i + 2])
return false;
}
}
return true;
}
// Driver code
public static void main(String[] args)
throws IOException
{
// Level order traversal
int[] level = new int[]{10, 15, 14, 25, 30};
if (isMinHeap(level))
System.out.println("True");
else
76
Chapter 15. Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap
System.out.println("False");
}
}
Output:
True
Source
https://www.geeksforgeeks.org/given-level-order-traversal-binary-tree-check-tree-min-heap/
77
Chapter 16
78
Chapter 16. Heap Sort for decreasing order using min heap
79
Chapter 16. Heap Sort for decreasing order using min heap
// Driver program
int main()
{
int arr[] = { 4, 6, 3, 2, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
Java
import java.io.*;
class GFG {
80
Chapter 16. Heap Sort for decreasing order using min heap
// Driver program
public static void main(String[] args)
{
int arr[] = { 4, 6, 3, 2, 9 };
int n = arr.length;
heapSort(arr, n);
C#
class GFG {
81
Chapter 16. Heap Sort for decreasing order using min heap
82
Chapter 16. Heap Sort for decreasing order using min heap
// Driver program
public static void Main()
{
int[] arr = { 4, 6, 3, 2, 9 };
int n = arr.Length;
heapSort(arr, n);
Output:
Sorted array is
9 6 4 3 2
Time complexity:It takes O(logn) for heapify and O(n) for constructing a heap.
Hence, the overall time complexity of heap sort using min heap or max heap is O(nlogn)
Source
https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/
83
Chapter 17
// Initializing a vector
vector<int> v1 = {20, 30, 40, 25, 15};
84
Chapter 17. Heap in C++ STL | make_heap(), push_heap(), pop_heap(), sort_heap(),
is_heap, is_heap_until()
return 0;
}
Output:
3. push_heap() :- This function is used to insert elements into heap. The size of the
heap is increased by 1. New element is placed appropriately in the heap.
4. pop_heap() :- This function is used to delete the maximum element of the heap.
The size of heap is decreased by 1. The heap elements are reorganised accordingly after this
operation.
// Initializing a vector
vector<int> v1 = {20, 30, 40, 25, 15};
85
Chapter 17. Heap in C++ STL | make_heap(), push_heap(), pop_heap(), sort_heap(),
is_heap, is_heap_until()
return 0;
}
Output:
5. sort_heap() :- This function is used to sort the heap. After this operation, the
container is no longer a heap.
// Initializing a vector
vector<int> v1 = {20, 30, 40, 25, 15};
86
Chapter 17. Heap in C++ STL | make_heap(), push_heap(), pop_heap(), sort_heap(),
is_heap, is_heap_until()
return 0;
}
Output:
6. is_heap() :- This function is used to check whether the container is heap or not.
Generally, in most implementations, the reverse sorted container is considered as heap.
Returns true if container is heap else returns false.
6. is_heap_until() :- This function returns the iterator to the position till the con-
tainer is the heap. Generally, in most implementations, the reverse sorted container
is considered as heap.
// Initializing a vector
vector<int> v1 = {40, 30, 25, 35, 15};
87
Chapter 17. Heap in C++ STL | make_heap(), push_heap(), pop_heap(), sort_heap(),
is_heap, is_heap_until()
return 0;
}
Output:
Improved By : SamirKhan
Source
https://www.geeksforgeeks.org/heap-using-stl-c/
88
Chapter 18
HeapSort
HeapSort - GeeksforGeeks
Heap sort is a comparison based sorting technique based on Binary Heap data structure. It
is similar to selection sort where we first find the maximum element and place the maximum
element at the end. We repeat the same process for remaining element.
What is Binary Heap?
Let us first define a Complete Binary Tree. A complete binary tree is a binary tree in which
every level, except possibly the last, is completely filled, and all nodes are as far left as
possible (Source Wikipedia)
A Binary Heap is a Complete Binary Tree where items are stored in a special order such that
value in a parent node is greater(or smaller) than the values in its two children nodes. The
former is called as max heap and the latter is called min heap. The heap can be represented
by binary tree or array.
Why array based representation for Binary Heap?
Since a Binary Heap is a Complete Binary Tree, it can be easily represented as array and
array based representation is space efficient. If the parent node is stored at index I, the left
child can be calculated by 2 * I + 1 and right child by 2 * I + 2 (assuming the indexing
starts at 0).
Heap Sort Algorithm for sorting in increasing order:
1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last
item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps while size of heap is greater than 1.
How to build the heap?
Heapify procedure can be applied to a node only if its children nodes are heapified. So the
heapification must be performed in the bottom up order.
Lets understand with the help of an example:
89
Chapter 18. HeapSort
C++
90
Chapter 18. HeapSort
// Driver program
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
91
Chapter 18. HeapSort
Java
92
Chapter 18. HeapSort
// Driver program
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
Python
93
Chapter 18. HeapSort
largest = r
# Build a maxheap.
for i in range(n, -1, -1):
heapify(arr, n, i)
C#
94
Chapter 18. HeapSort
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
95
Chapter 18. HeapSort
// Driver program
public static void Main()
{
int[] arr = {12, 11, 13, 5, 6, 7};
int n = arr.Length;
PHP
<?php
96
Chapter 18. HeapSort
}
}
// Driver program
$arr = array(12, 11, 13, 5, 6, 7);
$n = sizeof($arr)/sizeof($arr[0]);
heapSort($arr, $n);
printArray($arr , $n);
Output:
Sorted array is
97
Chapter 18. HeapSort
5 6 7 11 12 13
Snapshots:
98
Chapter 18. HeapSort
99
Chapter 18. HeapSort
Please write comments if you find anything incorrect, or you want to share more information
about the topic discussed above.
Improved By : Shivi_Aggarwal, Abby_akku
Source
https://www.geeksforgeeks.org/heap-sort/
100
Chapter 19
Input : N = 6
Output : 2
()
/ \
() ()
/ \ /
() () ()
Input : N = 9
Output :
()
/ \
() ()
/ \ / \
() () () ()
/ \
() ()
101
Chapter 19. Height of a complete binary tree (or Heap) with N nodes
N h
---------
1 0
2 1
3 1
4 2
5 2
.....
.....
C++
int height(int N)
{
return ceil(log2(N + 1)) - 1;
}
// driver node
int main()
{
int N = 6;
cout << height(N);
return 0;
}
Java
class GFG {
// Driver Code
102
Chapter 19. Height of a complete binary tree (or Heap) with N nodes
Python 3
# driver node
N = 6
print(height(N))
C#
class GFG {
static int height(int N)
{
return (int)Math.Ceiling(Math.Log(N
+ 1) / Math.Log(2)) - 1;
}
// Driver node
public static void Main()
{
int N = 6;
Console.Write(height(N));
}
}
103
Chapter 19. Height of a complete binary tree (or Heap) with N nodes
PHP
<?php
// PHP program to find height
// of complete binary tree
// from total nodes.
function height($N)
{
return ceil(log($N + 1, 2)) - 1;
}
// Driver Code
$N = 6;
echo height($N);
Output :
Source
https://www.geeksforgeeks.org/height-complete-binary-tree-heap-n-nodes/
104
Chapter 20
A Simple Solution is to first check root, if it’s greater than all of its descendants. Then
check for children of root. Time complexity of this solution is O(n2 )
105
Chapter 20. How to check if a given array represents a Binary Heap?
An Efficient Solution is to compare root only with its children (not all descendants), if
root is greater than its children and same is true for for all nodes, then tree is max-heap
(This conclusion is based on transitive property of > operator, i.e., if x > y and y > z, then
x > z).
The last internal node is present at index (2n-2)/2 assuming that indexing begins with 0.
Below is C++ implementation of this solution.
return false;
}
// Driver program
int main()
{
int arr[] = {90, 15, 10, 7, 12, 2, 7, 3};
int n = sizeof(arr) / sizeof(int);
return 0;
}
Output:
Yes
Time complexity of this solution is O(n). The solution is similar to preorder traversal of
Binary Tree.
106
Chapter 20. How to check if a given array represents a Binary Heap?
// Driver program
int main()
{
int arr[] = {90, 15, 10, 7, 12, 2, 7, 3};
int n = sizeof(arr) / sizeof(int);
return 0;
}
Output:
Yes
107
Chapter 20. How to check if a given array represents a Binary Heap?
Source
https://www.geeksforgeeks.org/how-to-check-if-a-given-array-represents-a-binary-heap/
108
Chapter 21
109
Chapter 21. How to implement stack using priority queue or heap?
110
Chapter 21. How to implement stack using priority queue or heap?
// Driver code
int main()
{
Stack* s=new Stack();
s->push(1);
s->push(2);
s->push(3);
while(!s->isEmpty()){
cout<<s->top()<<endl;
s->pop();
}
}
Output:
3
2
1
111
Chapter 21. How to implement stack using priority queue or heap?
Now, as we can see this implementation takes O(log n) time for both push and pop oper-
ations. This can be slightly optimized by using fibonacci heap implementation of priority
queue which would give us O(1) time complexity for push operation, but pop still requires
O(log n) time.
Source
https://www.geeksforgeeks.org/implement-stack-using-priority-queue-or-heap/
112
Chapter 22
113
Chapter 22. Huffman Coding | Greedy Algo-3
3. Create a new internal node with frequency equal to the sum of the two nodes frequencies.
Make the first extracted node as its left child and the other extracted node as its right child.
Add this node to the min heap.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is
the root node and the tree is complete.
Let us understand the algorithm with an example:
character Frequency
a 5
b 9
c 12
d 13
e 16
f 45
Step 1. Build a min heap that contains 6 nodes where each node represents root of a tree
with single node.
Step 2 Extract two minimum frequency nodes from min heap. Add a new internal node
with frequency 5 + 9 = 14.
Now min heap contains 5 nodes where 4 nodes are roots of trees with single element each,
and one heap node is root of tree with 3 elements
character Frequency
c 12
d 13
Internal Node 14
e 16
f 45
Step 3: Extract two minimum frequency nodes from heap. Add a new internal node with
frequency 12 + 13 = 25
Now min heap contains 4 nodes where 2 nodes are roots of trees with single element each,
and two heap nodes are root of tree with more than one nodes.
114
Chapter 22. Huffman Coding | Greedy Algo-3
character Frequency
Internal Node 14
e 16
Internal Node 25
f 45
Step 4: Extract two minimum frequency nodes. Add a new internal node with frequency
14 + 16 = 30
character Frequency
Internal Node 25
Internal Node 30
f 45
Step 5: Extract two minimum frequency nodes. Add a new internal node with frequency
25 + 30 = 55
character Frequency
f 45
Internal Node 55
Step 6: Extract two minimum frequency nodes. Add a new internal node with frequency
45 + 55 = 100
115
Chapter 22. Huffman Coding | Greedy Algo-3
character Frequency
Internal Node 100
Since the heap contains only one node, the algorithm stops here.
Steps to print codes from Huffman Tree:
Traverse the tree formed starting from the root. Maintain an auxiliary array. While moving
to the left child, write 0 to the array. While moving to the right child, write 1 to the array.
Print the array when a leaf node is encountered.
character code-word
f 0
c 100
d 101
a 1100
b 1101
e 111
116
Chapter 22. Huffman Coding | Greedy Algo-3
117
Chapter 22. Huffman Coding | Greedy Algo-3
return temp;
}
// current size is 0
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array
= (struct MinHeapNode**)malloc(minHeap->
capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
// A utility function to
// swap two min heap nodes
void swapMinHeapNode(struct MinHeapNode** a,
struct MinHeapNode** b)
118
Chapter 22. Huffman Coding | Greedy Algo-3
if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest],
&minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
++minHeap->size;
int i = minHeap->size - 1;
119
Chapter 22. Huffman Coding | Greedy Algo-3
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
int n = minHeap->size - 1;
int i;
printf("\n");
}
120
Chapter 22. Huffman Coding | Greedy Algo-3
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
{
struct MinHeapNode *left, *right, *top;
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
121
Chapter 22. Huffman Coding | Greedy Algo-3
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
{
// Construct Huffman Tree
struct MinHeapNode* root
= buildHuffmanTree(data, freq, size);
122
Chapter 22. Huffman Coding | Greedy Algo-3
return 0;
}
// For comparison of
// two heap nodes (needed in min heap)
struct compare {
{
return (l->freq > r->freq);
123
Chapter 22. Huffman Coding | Greedy Algo-3
}
};
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << "\n";
right = minHeap.top();
minHeap.pop();
124
Chapter 22. Huffman Coding | Greedy Algo-3
top->left = left;
top->right = right;
minHeap.push(top);
}
return 0;
}
Java
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Comparator;
int data;
char c;
HuffmanNode left;
HuffmanNode right;
}
125
Chapter 22. Huffman Coding | Greedy Algo-3
return;
}
// main function
public static void main(String[] args)
{
126
Chapter 22. Huffman Coding | Greedy Algo-3
// number of characters.
int n = 6;
char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
int[] charfreq = { 5, 9, 12, 13, 16, 45 };
hn.c = charArray[i];
hn.data = charfreq[i];
hn.left = null;
hn.right = null;
127
Chapter 22. Huffman Coding | Greedy Algo-3
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
Time complexity: O(nlogn) where n is the number of unique characters. If there are n
nodes, extractMin() is called 2*(n – 1) times. extractMin() takes O(logn) time as it calles
minHeapify(). So, overall complexity is O(nlogn).
If the input array is sorted, there exists a linear time algorithm. We will soon be discussing
in our next post.
Reference:
http://en.wikipedia.org/wiki/Huffman_coding
This article is compiled by Aashish Barnwal and reviewed by GeeksforGeeks team. Please
write comments if you find anything incorrect, or you want to share more information about
the topic discussed above.
Improved By : kddeepak
128
Chapter 22. Huffman Coding | Greedy Algo-3
Source
https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/
129
Chapter 23
Huffman Decoding
130
Chapter 23. Huffman Decoding
To decode the encoded data we require the Huffman tree. We iterate through the binary
encoded data. To find character corresponding to current bits, we use following simple steps.
The below code takes a string as input, it encodes it and save in a variable encodedString.
Then it decodes it and print the original string.
The below code performs full Huffman Encoding and Decoding of a given input data.
131
Chapter 23. Huffman Decoding
};
132
Chapter 23. Huffman Decoding
}
storeCodes(minHeap.top(), "");
}
133
Chapter 23. Huffman Decoding
Output:
Input: "geeksforgeeks"
Total number of character i.e. input length: 13
Size: 13 character occurrences * 8 bits = 104 bits or 13 bytes.
Input: "geeksforgeeks"
------------------------------------------------
Character | Frequency | Binary Huffman Value |
134
Chapter 23. Huffman Decoding
------------------------------------------------
e | 4 | 10 |
f | 1 | 1100 |
g | 2 | 011 |
k | 2 | 00 |
o | 1 | 010 |
r | 1 | 1101 |
s | 2 | 111 |
------------------------------------------------
Hence, we could see that after encoding the data we have saved a large amount of data.
The above method can also help us to determine the value of N i.e. the length of the encoded
data.
Source
https://www.geeksforgeeks.org/huffman-decoding/
135
Chapter 24
Implementation of Binomial
Heap
12------------10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
A Binomial Heap with 13 nodes. It is a collection of 3
Binomial Trees of orders 0, 2 and 3 from left to right.
10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
136
Chapter 24. Implementation of Binomial Heap
1. insert(H, k): Inserts a key ‘k’ to Binomial Heap ‘H’. This operation first creates a
Binomial Heap with single key ‘k’, then calls union on H and the new Binomial heap.
2. getMin(H): A simple way to getMin() is to traverse the list of root of Binomial Trees
and return the minimum key. This implementation requires O(Logn) time. It can be
optimized to O(1) by maintaining a pointer to minimum key root.
3. extractMin(H): This operation also uses union(). We first call getMin() to find
the minimum key Binomial Tree, then we remove the node and create a new Binomial
Heap by connecting all subtrees of the removed minimum node. Finally we call union()
on H and the newly created Binomial Heap. This operation requires O(Logn) time.
return b1;
}
137
Chapter 24. Implementation of Binomial Heap
138
Chapter 24. Implementation of Binomial Heap
{
if (_heap.size() <= 1)
return _heap;
list<Node*> new_heap;
list<Node*>::iterator it1,it2,it3;
it1 = it2 = it3 = _heap.begin();
if (_heap.size() == 2)
{
it2 = it1;
it2++;
it3 = _heap.end();
}
else
{
it2++;
it3=it2;
it3++;
}
while (it1 != _heap.end())
{
// if only one element remains to be processed
if (it2 == _heap.end())
it1++;
139
Chapter 24. Implementation of Binomial Heap
return adjust(temp);
}
140
Chapter 24. Implementation of Binomial Heap
return heap;
}
141
Chapter 24. Implementation of Binomial Heap
new_heap = adjust(new_heap);
return new_heap;
}
142
Chapter 24. Implementation of Binomial Heap
return 0;
}
Output:
Source
https://www.geeksforgeeks.org/implementation-binomial-heap/
143
Chapter 25
Implementation of Binomial
Heap | Set – 2 (delete() and
decreseKey())
1. insert(H, k): Inserts a key ‘k’ to Binomial Heap ‘H’. This operation first creates a
Binomial Heap with single key ‘k’, then calls union on H and the new Binomial heap.
2. getMin(H): A simple way to getMin() is to traverse the list of root of Binomial Trees
and return the minimum key. This implementation requires O(Logn) time. It can be
optimized to O(1) by maintaining a pointer to minimum key root.
3. extractMin(H): This operation also uses union(). We first call getMin() to find
the minimum key Binomial Tree, then we remove the node and create a new Binomial
Heap by connecting all subtrees of the removed minimum node. Finally we call union()
on H and the newly created Binomial Heap. This operation requires O(Logn) time.
Examples:
12------------10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
A Binomial Heap with 13 nodes. It is a collection of 3
Binomial Trees of orders 0, 2 and 3 from left to right.
144
Chapter 25. Implementation of Binomial Heap | Set – 2 (delete() and decreseKey())
10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
1. delete(H): Like Binary Heap, delete operation first reduces the key to minus infinite,
then calls extractMin().
2. decreaseKey(H): decreaseKey() is also similar to Binary Heap. We compare the
decreases key with it parent and if parent’s key is more, we swap keys and recur for
parent. We stop when we either reach a node whose parent has smaller key or we hit
the root node. Time complexity of decreaseKey() is O(Logn)
// Structure of Node
struct Node
{
int val, degree;
Node *parent, *child, *sibling;
};
// create a Node
Node *createNode(int n)
{
145
Chapter 25. Implementation of Binomial Heap | Set – 2 (delete() and decreseKey())
// define a Node
Node *res = NULL;
// if h2 is greater
else
{
Node *sib = h2->sibling;
h2->sibling = h1;
146
Chapter 25. Implementation of Binomial Heap | Set – 2 (delete() and decreseKey())
h2 = sib;
}
}
return res;
}
else
{
if (curr->val <= next->val)
{
curr->sibling = next->sibling;
binomialLink(next, curr);
}
else
{
if (prev == NULL)
res = next;
else
prev->sibling = next;
binomialLink(curr, next);
curr = next;
}
}
147
Chapter 25. Implementation of Binomial Heap | Set – 2 (delete() and decreseKey())
next = curr->sibling;
}
return res;
}
148
Chapter 25. Implementation of Binomial Heap | Set – 2 (delete() and decreseKey())
Node *curr = h;
while (curr->sibling != NULL)
{
if ((curr->sibling)->val < min)
{
min = (curr->sibling)->val;
min_node_prev = curr;
min_node = curr->sibling;
}
curr = curr->sibling;
}
149
Chapter 25. Implementation of Binomial Heap | Set – 2 (delete() and decreseKey())
if (res != NULL)
return res;
// Driver code
int main()
{
150
Chapter 25. Implementation of Binomial Heap | Set – 2 (delete() and decreseKey())
display(root);
return 0;
}
Output:
Source
https://www.geeksforgeeks.org/implementation-binomial-heap-set-2/
151
Chapter 26
Iterative HeapSort
Input : 10 20 15 17 9 21
Output : 9 10 15 17 20 21
Input: 12 11 13 5 6 7 15 5 19
Output: 5 5 6 7 11 12 13 15 19
152
Chapter 26. Iterative HeapSort
15 10 9 17 20 21
10 9 15 17 20 21
9 10 15 17 20 21
Here, underlined part is sorted part.
do
153
Chapter 26. Iterative HeapSort
{
index = (2 * j + 1);
j = index;
printf("\n\n");
heapSort(arr, n);
return 0;
}
Output :
Given array: 10 20 15 17 9 21
154
Chapter 26. Iterative HeapSort
Sorted array: 9 10 15 17 20 21
Here, both function buildMaxHeap and heapSort runs in O(nlogn) time. So, overall time
complexity is O(nlogn)
Source
https://www.geeksforgeeks.org/iterative-heap-sort/
155
Chapter 27
Solution: In the optimum sequence of jobs, the total volume of goods left at the end of all
jobs is 222.503
Example-2:
Solution: In the optimum sequence of jobs the total volume of goods left at the end of all
jobs is 145.72
156
Chapter 27. Job Selection Problem – Loss Minimization Strategy | Set 2
Explanation –
Since this is an optimization problem, we can try to solve this problem by using a greedy
algorithm. On each day we make a selection from among the goods that are yet to be
produced. Thus all we need is a local selection criteria or heuristic, which when applied to
select the jobs will give us the optimum result.
Instead of trying to maximize the volume, we can also try to minimize the losses. Since the
total volume that can be obtained from all goods is also constant, if we minimize the losses
we are guaranteed to get the optimum answer.
Now consider any good having volume V
Loss after Day 1: PV
Loss after Day 2: PV + P(1-P)V or V(2P-P^2)
Loss after Day 3: V(2P-P^2) + P(1 – 2P + P^2)V or V(3P – 3P^2 + P^3)
As the day increases the losses too increase. So the trick would be to ensure that the goods
are not kept idle after production. Further, since we are required to produce at least one
job per day, we should perform low volume jobs, and then perform the high volume jobs.
This strategy works due to two factors.
So in order to obtain the optimum solution we produce the larger volume goods later on.
For the first day select the good with least volume and produce it. Remove the produced
good from the list of goods. For the next day repeat the same. Keep repeating while there
are goods left to be produced.
When calculating the total volume at the end of production, keep in mind the the
good produced on day i, will have times its volume left. Ev-
idently, the good produced on day N (last day) will have its volume intact since
.
Algorithm –
Complexity –
We perform exactly N push() and pop() operations each of which takes log (N) time. Hence
time complexity is O( N * log(N) ).
157
Chapter 27. Job Selection Problem – Loss Minimization Strategy | Set 2
#include <bits/stdc++.h>
using namespace std;
// Print result
cout << endl << result << endl;
}
// Driver code
int main()
{
// For implementation simplicity days are numbered
// from 1 to N. Hence 1 based indexing is used
vector<int> V{ -1, 3, 5, 4, 1, 2, 7, 6, 8, 9, 10 };
158
Chapter 27. Job Selection Problem – Loss Minimization Strategy | Set 2
double P = 0.10;
optimum_sequence_jobs(V, P);
return 0;
}
Output –
1 2 3 4 5 6 7 8 9 10
41.3811
Source
https://www.geeksforgeeks.org/job-selection-problem-loss-minimization-strategy-set-2/
159
Chapter 28
160
Chapter 28. K maximum sum combinations from two arrays
C++
// Driver Code.
int main()
{
int A[] = { 4, 2, 5, 1 };
int B[] = { 8, 0, 5, 3 };
int N = sizeof(A)/sizeof(A[0]);
int K = 3;
NMaxCombinations(A, B, N, K);
return 0;
}
Java
161
Chapter 28. K maximum sum combinations from two arrays
// maximum combinations
// from two arrays,
import java.io.*;
import java.util.*;
class GFG {
NMaxCombinations(A, B, N, K);
}
}
162
Chapter 28. K maximum sum combinations from two arrays
Python 3
# max heap.
pq = PriorityQueue()
# Driver method
A = [ 4, 2, 5, 1 ]
B = [ 8, 0, 5, 3 ]
N = len(A)
K = 3
NMaxCombinations(A, B, N, K)
Output:
13
12
10
163
Chapter 28. K maximum sum combinations from two arrays
int N = A.size();
164
Chapter 28. K maximum sum combinations from two arrays
// with sum.
pq.push(make_pair(A[N - 1] + B[N - 1],
make_pair(N-1, N-1)));
my_set.insert(make_pair(N - 1, N - 1));
// iterate upto K
for (int count=0; count<K; count++) {
int i = temp.second.first;
int j = temp.second.second;
// Driver Code.
165
Chapter 28. K maximum sum combinations from two arrays
int main()
{
vector<int> A = { 1, 4, 2, 3 };
vector<int> B = { 2, 5, 1, 6 };
int K = 4;
NMaxCombinations(A, B, K);
return 0;
}
Output :
10
9
9
8
Time Complexity :
O(N log N) assuming K <= N
Improved By : nikhil741
Source
https://www.geeksforgeeks.org/k-maximum-sum-combinations-two-arrays/
166
Chapter 29
K-ary Heap
167
Chapter 29. K-ary Heap
• K-ary heap when used in the implementation of priority queue allows faster decrease
key operation as compared to binary heap ( O(log2 n)) for binary heap vs O(logk n)
for K-ary heap). Nevertheless, it causes the complexity of extractMin() operation
to increase to O(k log k n) as compared to the complexity of O(log2 n) when using
binary heaps for priority queue. This allows K-ary heap to be more efficient in
algorithms where decrease priority operations are more common than extractMin()
operation.Example: Dijkstra’s algorithm for single source shortest path and Prim’s
algorithm for minimum spanning tree
• K-ary heap has better memory cache behaviour than a binary heap which allows them
to run more quickly in practice, although it has a larger worst case running time of
both extractMin() and delete() operation (both being O(k log k n) ).
Implementation
Assuming 0 based indexing of array, an array represents a K-ary heap such that for any
node we consider:
• Parent of the node at index i (except root node) is located at index (i-1)/k
• Children of the node at index i are at indices (k*i)+1 , (k*i)+2 …. (k*i)+k
• The last non-leaf node of a heap of size n is located at index (n-2)/k
168
Chapter 29. K-ary Heap
while (1)
{
// child[i]=-1 if the node is a leaf
// children (no children)
for (int i=1; i<=k; i++)
child[i] = ((k*index + i) < len) ?
(k*index + i) : -1;
// leaf node
if (max_child == -1)
break;
169
Chapter 29. K-ary Heap
index = max_child_index;
}
}
170
Chapter 29. K-ary Heap
return max;
}
// Driver program
int main()
{
const int capacity = 100;
int arr[capacity] = {4, 5, 6, 7, 8, 9, 10};
int n = 7;
int k = 3;
buildHeap(arr, n, k);
int element = 3;
171
Chapter 29. K-ary Heap
return 0;
}
Output
Built Heap :
10 9 6 7 8 4 5
Extracted max is 10
• For a k-ary heap, with n nodes the maximum height of the given heap will be logk n. So
restoreUp() run for maximum of logk n times (as at every iteration the node is shifted
one level up is case of restoreUp() or one level down in case of restoreDown).
• restoreDown() calls itself recursively for k children. So time complexity of this func-
tions is O(k logk n).
• Insert and decreaseKey() operations call restoreUp() once. So complexity is O(logk n).
• Since extractMax() calls restoreDown() once, its complexity O(k logk n)
• Time complexity of build heap is O(n) (Analysis is similar to binary heap)
Source
https://www.geeksforgeeks.org/k-ary-heap/
172
Chapter 30
A brute force approach approach is to store all the contiguous sums in another array and
sort it, and print the k-th largest. But in case of number of elements being large, the array
in which we store the contiguous sums will run out of memory as the number of contiguous
subarrays will be large (quadratic order)
An efficient approach is store the pre-sum of the array in a sum[] array. We can find sum
of contiguous subarray from index i to j as sum[j]-sum[i-1]
Now for storing the Kth largest sum, use a min heap (priority queue) in which we push the
contiguous sums till we get K elements, once we have our K elements, check if the element
173
Chapter 30. K-th Largest Sum Contiguous Subarray
if greater then the Kth element it is inserted to the min heap with popping out the top
element in the min-heap, else not inserted . At the end the top element in the min-heap
will be your answer.
Below is the implementation of above approach.
C++
else
{
// it the min heap has equal to
174
Chapter 30. K-th Largest Sum Contiguous Subarray
Java
class KthLargestSumSubArray
{
// function to calculate kth largest
// element in contiguous subarray sum
static int kthLargestSum(int arr[], int n, int k)
{
// array to store predix sums
int sum[] = new int[n + 1];
sum[0] = 0;
sum[1] = arr[0];
for (int i = 2; i <= n; i++)
175
Chapter 30. K-th Largest Sum Contiguous Subarray
else
{
// it the min heap has equal to
// k elements then just check
// if the largest kth element is
// smaller than x then insert
// else its of no use
if (Q.peek() < x)
{
Q.poll();
Q.add(x);
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = new int[]{ 10, -10, 20, -40 };
176
Chapter 30. K-th Largest Sum Contiguous Subarray
int n = a.length;
int k = 6;
Output:
-10
Source
https://www.geeksforgeeks.org/k-th-largest-sum-contiguous-subarray/
177
Chapter 31
Input:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}
k = 3
Output: {_, _, 10, 11, 20, 40, 50, 50, ...}
178
Chapter 31. Kth smallest element after every insertion
// Driver code
int main()
{
int arr[] = {10, 20, 11, 70, 50, 40, 100, 55};
int k = 3;
int n = sizeof(arr)/sizeof(arr[0]);
kthLargest(arr, n, k);
return 0;
}
Output:
_ _ 10 11 20 40 55
If stream contains elements of non-primitive types, we may define our own compactor func-
tion and create a priority_queue accordingly.
179
Chapter 31. Kth smallest element after every insertion
Source
https://www.geeksforgeeks.org/kth-smallest-element-after-every-insertion/
180
Chapter 32
Kth smallest element in a row-wise and column-wise sorted 2D array | Set 1 - GeeksforGeeks
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Find
the kth smallest element in the given 2D array.
For example, consider the following 2D array.
181
Chapter 32. Kth smallest element in a row-wise and column-wise sorted 2D array | Set 1
#include<climits>
using namespace std;
182
Chapter 32. Kth smallest element in a row-wise and column-wise sorted 2D array | Set 1
HeapNode hr;
for (int i = 0; i < k; i++)
{
// Get current heap root
hr = harr[0];
// Heapify root
minHeapify(harr, 0, n);
}
Output:
183
Chapter 32. Kth smallest element in a row-wise and column-wise sorted 2D array | Set 1
Source
https://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/
184
Chapter 33
185
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
Java
class GFG
{
// Function to return k'th smallest
// element in a given array
public static int kthSmallest(Integer [] arr,
int k)
{
// Sort the given array
Arrays.sort(arr);
// driver program
public static void main(String[] args)
{
Integer arr[] = new Integer[]{12, 3, 5, 7, 19};
int k = 2;
System.out.print( "K'th smallest element is "+
kthSmallest(arr, k) );
186
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
}
}
C#
class GFG {
// driver program
public static void Main()
{
int []arr = new int[]{12, 3, 5,
7, 19};
int k = 2;
Console.Write( "K'th smallest element"
+ " is "+ kthSmallest(arr, k) );
}
}
PHP
<?php
// Simple PHP program to find
// k'th smallest element
187
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
// Driver Code
$arr = array(12, 3, 5, 7, 19);
$n =count($arr);
$k = 2;
echo "K'th smallest element is "
, kthSmallest($arr, $n, $k);
188
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
MinHeapify(0);
}
heap_size--;
return root;
}
189
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
// Return root
return mh.getMin();
}
Output:
190
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
191
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
maxHeapify(i);
i--;
}
}
// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
maxHeapify(0);
}
heap_size--;
return root;
}
192
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
*x = *y;
*y = temp;
}
// Return root
return mh.getMax();
}
Output:
Method 4 (QuickSelect)
This is an optimization over method 1 if QuickSortis used as a sorting algorithm in first
step. In QuickSort, we pick a pivot element, then move the pivot element to its correct
position and partition the array around it. The idea is, not to do complete quicksort, but
stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left
and right sides of pivot, but recur for one of them according to the position of pivot. The
worst case time complexity of this method is O(n2 ), but it works in O(n) on average.
C++
#include<iostream>
#include<climits>
using namespace std;
193
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);
194
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
}
swap(&arr[i], &arr[r]);
return i;
}
Java
class GFG
{
// Standard partition process of QuickSort.
// It considers the last element as pivot
// and moves all smaller element to left of
// it and greater elements to right
public static int partition(Integer [] arr, int l,
int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
//Swapping arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
195
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
return i;
}
// If position is same as k
if (pos-l == k-1)
return arr[pos];
196
Chapter 33. K’th Smallest/Largest Element in Unsorted Array | Set 1
Output:
There are two more solutions which are better than above discussed ones: One solution
is to do randomized version of quickSelect() and other solution is worst case linear time
algorithm (see the following posts).
K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)
References:
http://www.ics.uci.edu/~eppstein/161/960125.html
http://www.cs.rit.edu/~ib/Classes/CS515_Spring12-13/Slides/022-SelectMasterThm.pdf
Improved By : nitin mittal, vt_m
Source
https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/
197
Chapter 34
Input:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}
k = 3
198
Chapter 34. K’th largest element in a stream
void MinHeap::buildHeap()
{
int i = (heap_size - 1)/2;
199
Chapter 34. K’th largest element in a stream
while (i >= 0)
{
MinHeapify(i);
i--;
}
}
// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
MinHeapify(0);
}
heap_size--;
return root;
}
200
Chapter 34. K’th largest element in a stream
{
int temp = *x;
*x = *y;
*y = temp;
}
while (1)
{
// Take next element from stream
cout << "Enter next element of stream ";
cin >> x;
else
{
// If this is k'th element, then store it
// and build the heap created above
if (count == k-1)
{
arr[count] = x;
mh.buildHeap();
}
else
{
// If next element is greater than
// k'th largest, then replace the root
if (x > mh.getMin())
mh.replaceMin(x); // replaceMin calls
// heapify()
}
201
Chapter 34. K’th largest element in a stream
Output
K is 3
Enter next element of stream 23
Enter next element of stream 10
Enter next element of stream 15
K'th largest element is 10
Enter next element of stream 70
K'th largest element is 15
Enter next element of stream 5
K'th largest element is 15
Enter next element of stream 80
K'th largest element is 23
Enter next element of stream 100
K'th largest element is 70
Enter next element of stream
CTRL + C pressed
This article is contributed by Shivam Gupta. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Source
https://www.geeksforgeeks.org/kth-largest-element-in-a-stream/
202
Chapter 35
• A vector of integer pairs has been used to represent the cache, where each pair consists
of the block number and the number of times it has been used. The vector is ordered
in the form of a min-heap, which allows us to access the least frequently used block in
constant time.
• A hashmap has been used to store the indices of the cache blocks which allows searching
in constant time.
203
Chapter 35. LFU (Least Frequently Used) Cache Implementation
204
Chapter 35. LFU (Least Frequently Used) Cache Implementation
++v[i].second;
heapify(v, m, i, n);
}
if (n == v.size()) {
m.erase(v[0].first);
cout << "Cache block " << v[0].first
<< " removed.\n";
v[0] = v[--n];
heapify(v, m, 0, n);
}
v[n++] = make_pair(value, 1);
m.insert(make_pair(value, n - 1));
int i = n - 1;
// Driver Code
int main()
{
int cache_max_size = 4, cache_size = 0;
vector<pair<int, int> > cache(cache_max_size);
unordered_map<int, int> indices;
refer(cache, indices, 1, cache_size);
refer(cache, indices, 2, cache_size);
205
Chapter 35. LFU (Least Frequently Used) Cache Implementation
Output:
Source
https://www.geeksforgeeks.org/lfu-least-frequently-used-cache-implementation/
206
Chapter 36
Largest Derangement of a
Sequence
A derangement is any permutation of , such that no two elements at the same position
in and are equal.
Since we are interested in generating largest derangement, we start putting larger elements
in more significant positions.
Start from left, at any position place the next largest element among the values of the
sequence which have not yet been placed in positions before .
To scan all positions takes N iteration. In each iteration we are required to find a maximum
207
Chapter 36. Largest Derangement of a Sequence
However if we use a data structure like max-heap to find the maximum element, then the
complexity reduces to
Below is C++ implementation.
// Driver code
208
Chapter 36. Largest Derangement of a Sequence
int main()
{
int seq[] = { 92, 3, 52, 13, 2, 31, 1 };
int n = sizeof(seq)/sizeof(seq[0]);
printLargest(seq, n);
return 0;
}
Output:
Sequence:
92 3 52 13 2 31 1
Largest Derangement
52 92 31 3 13 1 2
Note:
The method can be easily modified to obtain the smallest derangement as well.
Instead of a Max Heap, we should use a Min Heap to consecutively get minimum elements
Source
https://www.geeksforgeeks.org/largest-derangement-sequence/
209
Chapter 37
210
Chapter 37. Largest triplet product in a stream
// Reinsert x, y, z in priority_queue
int ans = x*y*z;
cout << ans << endl;
q.push(x);
q.push(y);
q.push(z);
}
}
return ;
}
// Driver Function
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
211
Chapter 37. Largest triplet product in a stream
LargestTripletMultiplication(arr, n);
return 0;
}
Output:
-1
-1
6
24
60
Source
https://www.geeksforgeeks.org/largest-triplet-product-stream/
212
Chapter 38
10
/ \
20 100
/
30
Let us represent this in the form of an array Arr whose index starts from 1 :
we have:
Arr[1] = 10
Arr[2] = 20
Arr[3] = 100
Arr[4] = 30
If we observe, the first leaf (i.e. 100) starts from the index 3. Following it Arr[4] is also a
leaf.
By carefully analyzing, the following conclusion is observed:
213
Chapter 38. Leaf starting point in a Binary Heap data structure
The first leaf in a Heap starts from [floor(n/2)]+1 and all the nodes following
it till
n are leaves.
If we consider 0 as starting index, then leaves starts from floor(n/2) and exist
till end, i.e., (n-1).
Source
https://www.geeksforgeeks.org/leaf-starting-point-binary-heap-data-structure/
214
Chapter 39
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 subtree 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.
215
Chapter 39. Leftist Tree / Leftist Heap
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 :
Source : http://courses.cs.washington.edu/courses/cse326/08sp/lectures/05-leftist-heaps.
pdf
Detailed Steps for Merge:
216
Chapter 39. Leftist Tree / Leftist Heap
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.
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:
The subtree at node 7 violates the property of leftist heap so we swap it with the left child
217
Chapter 39. Leftist Tree / Leftist Heap
218
Chapter 39. Leftist Tree / Leftist Heap
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.
Another example of merging two leftist heap:
219
Chapter 39. Leftist Tree / Leftist Heap
220
Chapter 39. Leftist Tree / Leftist Heap
this->element = element;
right = rt;
left = lt,
dist = np;
}
};
//Class Declaration
class LeftistHeap
{
public:
LeftistHeap();
LeftistHeap(LeftistHeap &rhs);
~LeftistHeap();
bool isEmpty();
bool isFull();
int &findMin();
void Insert(int &x);
void deleteMin();
void deleteMin(int &minItem);
void makeEmpty();
void Merge(LeftistHeap &rhs);
LeftistHeap & operator =(LeftistHeap &rhs);
private:
LeftistNode *root;
LeftistNode *Merge(LeftistNode *h1,
LeftistNode *h2);
LeftistNode *Merge1(LeftistNode *h1,
LeftistNode *h2);
void swapChildren(LeftistNode * t);
void reclaimMemory(LeftistNode * t);
LeftistNode *clone(LeftistNode *t);
};
// Copy constructor.
LeftistHeap::LeftistHeap(LeftistHeap &rhs)
{
root = NULL;
*this = rhs;
}
221
Chapter 39. Leftist Tree / Leftist Heap
LeftistHeap::~LeftistHeap()
{
makeEmpty( );
}
222
Chapter 39. Leftist Tree / Leftist Heap
223
Chapter 39. Leftist Tree / Leftist Heap
{
return root == NULL;
}
// Deep copy
LeftistHeap &LeftistHeap::operator =(LeftistHeap & rhs)
{
if (this != &rhs)
{
makeEmpty();
root = clone(rhs.root);
}
return *this;
}
224
Chapter 39. Leftist Tree / Leftist Heap
//Driver program
int main()
{
LeftistHeap h;
LeftistHeap h1;
LeftistHeap h2;
int x;
int arr[]= {1, 5, 7, 10, 15};
int arr1[]= {22, 75};
h.Insert(arr[0]);
h.Insert(arr[1]);
h.Insert(arr[2]);
h.Insert(arr[3]);
h.Insert(arr[4]);
h1.Insert(arr1[0]);
h1.Insert(arr1[1]);
h.deleteMin(x);
cout<< x <<endl;
h1.deleteMin(x);
cout<< x <<endl;
h.Merge(h1);
h2 = h;
h2.deleteMin(x);
cout<< x << endl;
return 0;
}
Output:
1
22
5
References:
Wikipedia- Leftist Tree
CSC378: Leftist Trees
225
Chapter 39. Leftist Tree / Leftist Heap
Source
https://www.geeksforgeeks.org/leftist-tree-leftist-heap/
226
Chapter 40
Input : arr[] = 1 2 3 4 5
m = 4
Output : 4
The maximum four elements are 2, 3,
4 and 5. The minimum four elements are
1, 2, 3 and 4. The difference between
two sums is (2 + 3 + 4 + 5) - (1 + 2
+ 3 + 4) = 4
Input : arr[] = 5 8 11 40 15
m = 2
Output : 42
The difference is (40 + 15) - (5 + 8)
The idea is to first sort the array, then find sum of first m elements and sum of last m
elements. Finally return difference between two sums.
CPP
227
Chapter 40. Maximum difference between two subsets of m elements
#include <iostream>
using namespace std;
// utility function
int find_difference(int arr[], int n, int m)
{
int max = 0, min = 0;
// sort array
sort(arr, arr + n);
for (int i = 0, j = n - 1;
i < m; i++, j--) {
min += arr[i];
max += arr[j];
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 4;
cout << find_difference(arr, n, m);
return 0;
}
Java
class GFG {
// utility function
static int find_difference(int arr[], int n,
int m)
{
int max = 0, min = 0;
// sort array
Arrays.sort(arr);
for (int i = 0, j = n - 1;
i < m; i++, j--) {
228
Chapter 40. Maximum difference between two subsets of m elements
min += arr[i];
max += arr[j];
}
// Driver program
public static void main(String arg[])
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int m = 4;
System.out.print(find_difference(arr, n, m));
}
}
Python3
# Python program to
# find difference
# between max and
# min sum of array
# sort array
arr.sort();
j = n-1
for i in range(m):
min += arr[i]
max += arr[j]
j = j - 1
# Driver code
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5]
n = len(arr)
m = 4
print(find_difference(arr, n, m))
229
Chapter 40. Maximum difference between two subsets of m elements
# Harshit Saini
C#
class GFG {
// utility function
static int find_difference(int[] arr, int n,
int m)
{
int max = 0, min = 0;
// sort array
Array.Sort(arr);
for (int i = 0, j = n - 1;
i < m; i++, j--) {
min += arr[i];
max += arr[j];
}
// Driver program
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
int m = 4;
Console.Write(find_difference(arr, n, m));
}
}
PHP
<?php
// PHP program to find difference
// between max and min sum of array
// utility function
230
Chapter 40. Maximum difference between two subsets of m elements
// sort array
sort($arr);
sort( $arr,$n);
// Driver code
{
$arr = array(1, 2, 3, 4, 5);
$n = sizeof($arr) / sizeof($arr[0]);
$m = 4;
echo find_difference($arr, $n, $m);
return 0;
}
Output:
We can optimize the above solution using more efficient approaches discussed in below post.
k largest(or smallest) elements in an array | added Min Heap method
Improved By : nitin mittal, SanyamAggarwal
Source
https://www.geeksforgeeks.org/difference-maximum-sum-minimum-sum-n-m-elementsin-review/
231
Chapter 41
232
Chapter 41. Maximum distinct elements after removing k elements
#include <bits/stdc++.h>
using namespace std;
while (k--) {
233
Chapter 41. Maximum distinct elements after removing k elements
int k = 3;
cout << "Maximum distinct elements = "
<< maxDistinctNum(arr, n, k);
return 0;
}
Output:
Time Complexity: O(k*logd), where d is the number of distinct elements in the given array.
Source
https://www.geeksforgeeks.org/maximum-distinct-elements-removing-k-elements/
234
Chapter 42
Making it clear, when the input size is odd, we take the middle element of sorted data. If
the input size is even, we pick average of middle two elements in sorted stream.
Note that output is effective median of integers read from the stream so far. Such an
algorithm is called online algorithm. Any algorithm that can guarantee output of i-elements
after processing i-th element, is said to be online algorithm. Let us discuss three solutions
for the above problem.
Method 1: Insertion Sort
If we can sort the data as it appears, we can easily locate median element. Insertion Sort is
one such online algorithm that sorts the data appeared so far. At any instance of sorting, say
after sorting i-th element, the first i elements of array are sorted. The insertion sort doesn’t
depend on future data to sort data input till that point. In other words, insertion sort
considers data sorted so far while inserting next element. This is the key part of insertion
sort that makes it an online algorithm.
However, insertion sort takes O(n2 ) time to sort n elements. Perhaps we can use binary
search on insertion sort to find location of next element in O(log n) time. Yet, we can’t do
data movement in O(log n) time. No matter how efficient the implementation is, it takes
polynomial time in case of insertion sort.
235
Chapter 42. Median in a stream of integers (running integers)
#include <iostream>
using namespace std;
// Heap capacity
#define MAX_HEAP_SIZE (128)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
// exchange a and b
inline
void Exch(int &a, int &b)
{
int aux = a;
a = b;
b = aux;
}
236
Chapter 42. Median in a stream of integers (running integers)
{
return a > b;
}
// Signum function
// = 0 if a == b - heaps are balanced
// = -1 if a < b - left contains less elements than right
// = 1 if a > b - left contains more elements than right
int Signum(int a, int b)
{
if( a == b )
return 0;
return a < b ? -1 : 1;
}
// Heap implementation
// The functionality is embedded into
// Heap abstract class to avoid code duplication
class Heap
{
public:
// Initializes heap array and comparator required
// in heapification
Heap(int *b, bool (*c)(int, int)) : A(b), comp(c)
{
heapSize = -1;
}
237
Chapter 42. Median in a stream of integers (running integers)
protected:
int right(int i)
{
return 2 * (i + 1);
}
int parent(int i)
{
if( i <= 0 )
{
return -1;
}
return (i - 1)/2;
}
// Heap array
int *A;
// Comparator
bool (*comp)(int, int);
// Heap size
int heapSize;
return max;
}
238
Chapter 42. Median in a stream of integers (running integers)
// Heapification
// Note that, for the current median tracing problem
// we need to heapify only towards root, always
void heapify(int i)
{
int p = parent(i);
Exch(A[0], A[heapSize]);
heapSize--;
heapify(parent(heapSize+1));
}
return del;
}
239
Chapter 42. Median in a stream of integers (running integers)
heapSize++;
A[heapSize] = key;
heapify(heapSize);
}
return ret;
}
};
public:
MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }
~MaxHeap() { }
240
Chapter 42. Median in a stream of integers (running integers)
public:
~MinHeap() { }
241
Chapter 42. Median in a stream of integers (running integers)
l.Insert(e);
}
else
{
// current element fits in right (min) heap
r.Insert(e);
}
break;
case 0: // The left and right heaps contain same number of elements
break;
242
Chapter 42. Median in a stream of integers (running integers)
break;
}
return 0;
}
Time Complexity: If we omit the way how stream was read, complexity of median finding
is O(N log N), as we need to read the stream, and due to heap insertions/deletions.
At first glance the above code may look complex. If you read the code carefully, it is simple
algorithm.
243
Chapter 42. Median in a stream of integers (running integers)
Source
https://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
244
Chapter 43
Input: 5 10 15
Output: 5
7.5
10
Explanation: Given the input stream as an array of integers [5,10,15]. We will now read
integers one by one and print the median correspondingly. So, after reading first element
5,median is 5. After reading 10,median is 7.5 After reading 15 ,median is 10.
The idea is to use max heap and min heap to store the elements of higher half and lower half.
Max heap and min heap can be implemented using priority_queue in C++ STL. Below is
the step by step algorithm to solve this problem.
Algorithm:
245
Chapter 43. Median of Stream of Running Integers using STL
1. Create two heaps. One max heap to maintain elements of lower half and one min heap
to maintain elements of higher half at any point of time..
2. Take initial value of median as 0.
3. For every newly read element, insert it into either max heap or min heap and calulate
the median based on the following conditions:
• If the size of max heap is greater than size of min heap and the element is less
than previous median then pop the top element from max heap and insert into
min heap and insert the new element to max heap else insert the new element to
min heap. Calculate the new median as average of top of elements of both max
and min heap.
• If the size of max heap is less than size of min heap and the element is greater
than previous median then pop the top element from min heap and insert into
max heap and insert the new element to min heap else insert the new element to
max heap. Calculate the new median as average of top of elements of both max
and min heap.
• If the size of both heaps are same. Then check if current is less than previous
median or not. If the current element is less than previous median then insert it
to max heap and new median will be equal to top element of max heap. If the
current element is greater than previous median then insert it to min heap and
new median will be equal to top element of min heap.
246
Chapter 43. Median of Stream of Running Integers using STL
247
Chapter 43. Median of Stream of Running Integers using STL
Output:
5
10
10
12.5
10
Source
https://www.geeksforgeeks.org/median-of-stream-of-running-integers-using-stl/
248
Chapter 44
Input: k = 3, n = 4
list1 = 1->3->5->7->NULL
list2 = 2->4->6->8->NULL
list3 = 0->9->10->11
Output:
0->1->2->3->4->5->6->7->8->9->10->11
Method 1 (Simple)
A Simple Solution is to initialize result as first list. Now traverse all lists starting from
second list. Insert every node of currently traversed list into result in a sorted way. Time
complexity of this solution is O(N2 ) where N is total number of nodes, i.e., N = kn.
249
Chapter 44. Merge K sorted linked lists | Set 1
/* Base cases */
if (a == NULL)
return (b);
else if(b == NULL)
return (a);
250
Chapter 44. Merge K sorted linked lists | Set 1
return result;
}
return arr[0];
}
251
Chapter 44. Merge K sorted linked lists | Set 1
temp->next = NULL;
return temp;
}
arr[0] = newNode(1);
arr[0]->next = newNode(3);
arr[0]->next->next = newNode(5);
arr[0]->next->next->next = newNode(7);
arr[1] = newNode(2);
arr[1]->next = newNode(4);
arr[1]->next->next = newNode(6);
arr[1]->next->next->next = newNode(8);
arr[2] = newNode(0);
arr[2]->next = newNode(9);
arr[2]->next->next = newNode(10);
arr[2]->next->next->next = newNode(11);
printList(head);
return 0;
}
Output :
0 1 2 3 4 5 6 7 8 9 10 11
Time Complexity of above algorithm is O(nk logk) as outer while loop in function mergeK-
Lists() runs log k times and every time we are processing nk elements.
Merge k sorted linked lists | Set 2 (Using Min Heap)
252
Chapter 44. Merge K sorted linked lists | Set 1
Source
https://www.geeksforgeeks.org/merge-k-sorted-linked-lists/
253
Chapter 45
Input:
k = 3, n = 4
arr[][] = { {1, 3, 5, 7},
{2, 4, 6, 8},
{0, 9, 10, 11}} ;
Output: 0 1 2 3 4 5 6 7 8 9 10 11
A simple solution is to create an output array of size n*k and one by one copy all arrays
to it. Finally, sort the output array using any O(n Log n) sorting algorithm. This approach
takes O(nk Log nk) time.
One efficient solution is to first merge arrays into groups of 2. After first merging, we
have k/2 arrays. We again merge arrays in groups, now we have k/4 arrays. We keep doing it
unit we have one array left. The time complexity of this solution would O(nk Log k). How?
Every merging in first iteration would take 2n time (merging two arrays of size n). Since
there are total k/2 merging, total time in first iteration would be O(nk). Next iteration
would also take O(nk). There will be total O(Log k) iterations, hence time complexity is
O(nk Log k)
Another efficient solution is to use Min Heap. This Min Heap based solution has same
time complexity which is O(nk Log k). But for different sized arrays, this solution works
much better.
Following is detailed algorithm.
1. Create an output array of size n*k.
2. Create a min heap of size k and insert 1st element in all the arrays into the heap
254
Chapter 45. Merge k sorted arrays | Set 1
#define n 4
255
Chapter 45. Merge k sorted arrays | Set 1
return output;
}
256
Chapter 45. Merge k sorted arrays | Set 1
257
Chapter 45. Merge k sorted arrays | Set 1
return 0;
}
Output:
Merged array is
1 2 6 9 12 20 23 34 34 90 1000 2000
Time Complexity: The main step is 3rd step, the loop runs n*k times. In every iteration
of loop, we call heapify which takes O(Logk) time. Therefore, the time complexity is O(nk
Logk).
Merge k sorted arrays | Set 2 (Different Sized Arrays)
Thanks to vigneshfor suggesting this problem and initial solution. Please write comments if
you find anything incorrect, or you want to share more information about the topic discussed
above
Improved By : maxflex
Source
https://www.geeksforgeeks.org/merge-k-sorted-arrays/
258
Chapter 46
Input: k = 3
arr[][] = { {1, 3},
{2, 4, 6},
{0, 9, 10, 11}} ;
Output: 0 1 2 3 4 6 9 10 11
Input: k = 2
arr[][] = { {1, 3, 20},
{2, 4, 6}} ;
Output: 1 2 3 4 6 20
We have discussed a solution that works for all arrays of same size in Merge k sorted arrays
| Set 1.
A simple solution is to create an output array and and one by one copy all arrays to it.
Finally, sort the output array using. This approach takes O(N Logn N) time where N is
count of all elements.
An efficient solution is to use heap data structure. The time complexity of heap based
solution is O(N Log k).
1. Create an output array.
2. Create a min heap of size k and insert 1st element in all the arrays into the heap
3. Repeat following steps while priority queue is not empty.
259
Chapter 46. Merge k sorted arrays | Set 2 (Different Sized Arrays)
…..a) Remove minimum element from heap (minimum is always at root) and store it in
output array.
…..b) Insert next element from the array from which the element is extracted. If the array
doesn’t have any more elements, then do nothing.
output.push_back(curr.first);
260
Chapter 46. Merge k sorted arrays | Set 2 (Different Sized Arrays)
return output;
}
return 0;
}
Output:
Merged array is
1 2 6 9 12 23 34 90 2000
Source
https://www.geeksforgeeks.org/merge-k-sorted-arrays-set-2-different-sized-arrays/
261
Chapter 47
Input: k = 3, n = 4
list1 = 1->3->5->7->NULL
list2 = 2->4->6->8->NULL
list3 = 0->9->10->11
Output:
0->1->2->3->4->5->6->7->8->9->10->11
struct Node {
int data;
struct Node* next;
262
Chapter 47. Merge k sorted linked lists | Set 2 (Using Min Heap)
};
else {
// insert 'top' at the end of the merged list so far
263
Chapter 47. Merge k sorted linked lists | Set 2 (Using Min Heap)
last->next = top;
return new_node;
}
264
Chapter 47. Merge k sorted linked lists | Set 2 (Using Min Heap)
arr[1] = newNode(2);
arr[1]->next = newNode(4);
arr[1]->next->next = newNode(6);
arr[1]->next->next->next = newNode(8);
arr[2] = newNode(0);
arr[2]->next = newNode(9);
arr[2]->next->next = newNode(10);
arr[2]->next->next->next = newNode(11);
return 0;
}
Output:
0 1 2 3 4 5 6 7 8 9 10 11
Source
https://www.geeksforgeeks.org/merge-k-sorted-linked-lists-set-2-using-min-heap/
265
Chapter 48
The idea is simple. We create an array to store result. We copy both given arrays one by
one to result. Once we have copied all elements, we call standard build heap to construct
full merged max heap.
C++
266
Chapter 48. Merge two binary Max Heaps
return;
int l = 2 * idx + 1;
int r = 2 * idx + 2;
int max;
if (l < n && arr[l] > arr[idx])
max = l;
else
max = idx;
if (r < n && arr[r] > arr[max])
max = r;
// Driver code
int main()
{
267
Chapter 48. Merge two binary Max Heaps
return 0;
}
Java
class GfG {
268
Chapter 48. Merge two binary Max Heaps
arr[max] = arr[i];
arr[i] = temp;
maxHeapify(arr, n, max);
}
}
// Driver Code
public static void main(String[] args)
{
int[] a = {10, 5, 6, 2};
int[] b = {12, 7, 9};
int n = a.length;
int m = b.length;
mergeHeaps(merged, a, b, n, m);
C#
class GfG {
269
Chapter 48. Merge two binary Max Heaps
270
Chapter 48. Merge two binary Max Heaps
// Driver Code
public static void Main()
{
int[] a = {10, 5, 6, 2};
int[] b = {12, 7, 9};
int n = a.Length;
int m = b.Length;
mergeHeaps(merged, a, b, n, m);
Output:
12 10 9 2 5 7 6
Since time complexity for building the heap from array of n elements is O(n). The complexity
of merging the heaps is equal to O(n + m).
Improved By : nitin mittal
Source
https://www.geeksforgeeks.org/merge-two-binary-max-heaps/
271
Chapter 49
This problem has existing solution please refer Merge two sorted arrays link. We will solve
this problem in python using heapq.merge() in a single line of code.
def mergeArray(arr1,arr2):
return list(merge(arr1, arr2))
# Driver function
if __name__ == "__main__":
arr1 = [1,3,4,5]
arr2 = [2,4,6,8]
print mergeArray(arr1, arr2)
272
Chapter 49. Merge two sorted arrays in Python using heapq
Output:
[1, 2, 3, 4, 4, 5, 6, 8]
This module provides an implementation of the heap queue algorithm, also known as the
priority queue algorithm.
To create a heap, use a list initialized to [], or you can transform a populated list into a
heap via function heapify().The following functions are provided:
• heapq.heappush(heap,item) : Push the value item onto the heap, maintaining the
heap invariant.
• heapq.heappop(heap) : Pop and return the smallest item from the heap, maintain-
ing the heap invariant. If the heap is empty, IndexError is raised. To access the
smallest item without popping it, use heap[0].
• heapq.heappushpop(heap, item) : Push item on the heap, then pop and return
the smallest item from the heap. The combined action runs more efficiently than
heappush() followed by a separate call to heappop().
• heapq.heapify(x) : Transform list x into a heap, in-place, in linear time.
• heapq.merge(*iterables) : Merge multiple sorted inputs into a single sorted output
(for example, merge timestamped entries from multiple log files). Returns an iterator
over the sorted values.
Source
https://www.geeksforgeeks.org/merge-two-sorted-arrays-python-using-heapq/
273
Chapter 50
Minimum increment/decrement
to make array non-Increasing
Brute-Force approach : We consider both possibilities for every element and find the
minimum of two possibilities.
Efficient Approach : Calculate the sum of absolute differences between the final array
elements and the current array elements. Thus, the answer will be the sum of the difference
274
Chapter 50. Minimum increment/decrement to make array non-Increasing
between the ith element and the smallest element occurred till then. For this, we can
maintain a min-heap to find the smallest element encountered till now. In the min-priority
queue, we will put the elements and new elements are compared with the previous minimum.
If new minimum is found we will update it, this is done because each of the next element
which is coming should be smaller than the current minimum element found till. Here, we
calculate the difference so that we can get how much we have to change the current number
so that it will be equal or less than previous numbers encountered till. Lastly, the sum of
all these difference will be our answer as this will give the final value upto which we have
to change the elements.
Below is C++ implementation of the above approach
// min heap
priority_queue<int, vector<int>, greater<int> > pq;
return sum;
}
// Driver Code
int main()
{
275
Chapter 50. Minimum increment/decrement to make array non-Increasing
int a[] = { 3, 1, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
return 0;
}
Output:
Source
https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/
276
Chapter 51
Input : 11 8 5 7 5 100
k = 4
Output : 1400
The idea is simple, we find the smallest k elements and print multiplication of them. In
below implementation, we have used simple Heap based approach where we insert array
elements into a min heap and then find product of top k elements.
C++
277
Chapter 51. Minimum product of k integers in an array of positive Integers
{
priority_queue<int, vector<int>, greater<int> > pq;
for (int i = 0; i < n; i++)
pq.push(arr[i]);
return ans;
}
// Driver code
int main()
{
int arr[] = {198, 76, 544, 123, 154, 675};
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum product is "
<< minProduct(arr, n, k);
return 0;
}
Python3
heapq.heapify(arr)
count = 0
ans = 1
278
Chapter 51. Minimum product of k integers in an array of positive Integers
return ans;
# Driver method
arr = [198, 76, 544, 123, 154, 675]
k = 2
n = len(arr)
print ("Minimum product is",
minProduct(arr, n, k))
Output:
Source
https://www.geeksforgeeks.org/minimum-product-k-integers-array-positive-integers/
279
Chapter 52
Input: [6, 8, 4, 5, 2, 3]
Output: 604
The minimum sum is formed by numbers
358 and 246
Input: [5, 3, 0, 7, 4]
Output: 82
The minimum sum is formed by numbers
35 and 047
Since we want to minimize the sum of two numbers to be formed, we must divide all digits
in two halves and assign half-half digits to them. We also need to make sure that the
leading digits are smaller.
We build a Min Heap with the elements of the given array, which takes O(n) worst time.
Now we retrieve min values (2 at a time) of array, by polling from the Priority Queue and
append these two min values to our numbers, till the heap becomes empty, i.e., all the
elements of array get exhausted. We return the sum of two formed numbers, which is our
required answer.
C/C++
280
Chapter 52. Minimum sum of two numbers formed from digits of an array
int main()
{
int arr[] = {6, 8, 4, 5, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<minSum(arr, n)<<endl;
return 0;
}
281
Chapter 52. Minimum sum of two numbers formed from digits of an array
Java
class MinSum
{
// Returns sum of two numbers formed
// from all digits in a[]
public static long solve(int[] a)
{
// min Heap
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
return sum;
}
// Driver code
public static void main (String[] args)
{
int arr[] = {6, 8, 4, 5, 2, 3};
System.out.println("The required sum is "+ solve(arr));
}
}
282
Chapter 52. Minimum sum of two numbers formed from digits of an array
Output:
Source
https://www.geeksforgeeks.org/minimum-sum-two-numbers-formed-digits-array-2/
283
Chapter 53
Input : n = 3
Output : Assume the integers are 1, 2, 3.
Then the 2 possible max heaps are:
3
/ \
1 2
3
/ \
2 1
Input : n = 4
Output : Assume the integers are 1, 2, 3, 4.
Then the 3 possible max heaps are:
4
/ \
3 2
/
1
4
/ \
2 3
284
Chapter 53. Number of ways to form a heap with n distinct integers
/
1
4
/ \
3 1
/
2
Since there is only one element as the root, it must be the largest number. Now we have n-1
remaining elements. The main observation here is that because of the max heap properties,
the structure of the heap nodes will remain the same in all instances, but only the values
in the nodes will change.
Assume there are l elements in the left sub-tree and r elements in the right sub-tree.
Now for the root, l + r = n-1. From this we can see that we can choose any l of the
remaining n-1 elements for the left sub-tree as they are all smaller than the root.
We know the there are ways to do this. Next for each instance of these, we can
have many heaps with l elements and for each of those we can have many heaps with r
elements. Thus we can consider them as subproblems and recur for the final answer as:
heap h = . Also the maximum number of elements that can be present in the h
th level of any heap, m = , where the root is at the 0th level. Moreover the number of
elements actually present in the last level of the heap p = n – ( – 1). (since
number of nodes present till the penultimate level). Thus, there can be two cases: when
the last level is more than or equal to half-filled:
l= – 1, if p >= m / 2
(or) the last level is less than half-filled:
values of . Similarly if we look at the recursion tree for the optimal substructure
recurrence formed above, we can see that it also has overlapping subproblems property,
hence can be solved using dynamic programming:
T(7)
285
Chapter 53. Number of ways to form a heap with n distinct integers
/ \
T(3) T(3)
/ \ / \
T(1) T(1) T(1) T(1)
// to calculate nCk
int choose(int n, int k)
{
if (k > n)
return 0;
if (n <= 1)
return 1;
if (k == 0)
return 1;
if (nck[n][k] != -1)
return nck[n][k];
int h = log2[n];
286
Chapter 53. Number of ways to form a heap with n distinct integers
if (dp[n] != -1)
return dp[n];
287
Chapter 53. Number of ways to form a heap with n distinct integers
if (currPower2 == i) {
currLog2++;
currPower2 *= 2;
}
log2[i] = currLog2;
}
return numberOfHeaps(n);
}
// driver function
int main()
{
int n = 10;
cout << solve(n) << endl;
return 0;
}
Output:
3360
Source
https://www.geeksforgeeks.org/number-ways-form-heap-n-distinct-integers/
288
Chapter 54
Overview of Data Structures | Set 2 (Binary Tree, BST, Heap and Hash) - GeeksforGeeks
We have discussed Overview of Array, Linked List, Queue and Stack. In this article following
Data Structures are discussed.
5. Binary Tree
6. Binary Search Tree
7. Binary Heap
9. Hashing
Binary Tree
Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are
hierarchical data structures.
A binary tree is a tree data structure in which each node has at most two children, which
are referred to as the left child and the right child. It is implemented mainly using Links.
Binary Tree Representation: A tree is represented by a pointer to the topmost node in
tree. If the tree is empty, then value of root is NULL. A Binary Tree node contains following
parts.
1. Data
2. Pointer to left child
3. Pointer to right child
A Binary Tree can be traversed in two ways:
Depth First Traversal: Inorder (Left-Root-Right), Preorder (Root-Left-Right) and Postorder
(Left-Right-Root)
Breadth First Traversal: Level Order Traversal
Binary Tree Properties:
289
Chapter 54. Overview of Data Structures | Set 2 (Binary Tree, BST, Heap and Hash)
Examples : One reason to use binary tree or tree in general is for the things that form
a hierarchy. They are useful in File structures where each file is located in a particular
directory and there is a specific hierarchy associated with files and directories. Another
example where Trees are useful is storing heirarchical objects like JavaScript Document
Object Model considers HTML page as a tree with nesting of tags as parent child relations.
Binary Search Tree
In Binary Search Tree is a Binary Tree with following additional properties:
1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.
Time Complexities:
Search : O(h)
Insertion : O(h)
Deletion : O(h)
Extra Space : O(n) for pointers
h: Height of BST
n: Number of nodes in BST
BST provide moderate access/search (quicker than Linked List and slower than arrays).
BST provide moderate insertion/deletion (quicker than Arrays and slower than Linked
Lists).
Examples : Its main use is in search application where data is constantly entering/leaving
and data needs to printed in sorted order. For example in implementation in E- commerce
290
Chapter 54. Overview of Data Structures | Set 2 (Binary Tree, BST, Heap and Hash)
websites where a new product is added or product goes out of stock and all products are
lised in sorted order.
Binary Heap
A Binary Heap is a Binary Tree with following properties.
1) It’s a complete tree (All levels are completely filled except possibly the last level and the
last level has all keys as left as possible). This property of Binary Heap makes them suitable
to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at
root must be minimum among all keys present in Binary Heap. The same property must
be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.
It is mainly implemented using array.
Get Minimum in Min Heap: O(1) [Or Get Max in Max Heap]
Extract Minimum Min Heap: O(Log n) [Or Extract Max in Max Heap]
Decrease Key in Min Heap: O(Log n) [Or Extract Max in Max Heap]
Insert: O(Log n)
Delete: O(Log n)
Example : Used in implementing efficient priority-queues, which in turn are used for
scheduling processes in operating systems. Priority Queues are also used in Dijstra’s and
Prim’s graph algorithms.
The Heap data structure can be used to efficiently find the k smallest (or largest) elements
in an array, merging k sorted arrays, median of a stream, etc.
Heap is a special data structure and it cannot be used for searching of a particular element.
HashingHash Function: A function that converts a given big input key to a small practi-
cal integer value. The mapped integer value is used as an index in hash table. A good hash
function should have following properties
1) Efficiently computable.
2) Should uniformly distribute the keys (Each table position equally likely for each key)
Hash Table: An array that stores pointers to records corresponding to a given phone number.
An entry in hash table is NIL if no existing phone number has hash function value equal to
the index for the entry.
Collision Handling: Since a hash function gets us a small number for a key which is a big
integer or string, there is possibility that two keys result in same value. The situation where
a newly inserted key maps to an already occupied slot in hash table is called collision and
must be handled using some collision handling technique. Following are the ways to handle
collisions:
Chaining:The idea is to make each cell of hash table point to a linked list of records that
have same hash function value. Chaining is simple, but requires additional memory outside
the table.
Open Addressing: In open addressing, all elements are stored in the hash table itself. Each
table entry contains either a record or NIL. When searching for an element, we one by one
examine table slots until the desired element is found or it is clear that the element is not
in the table.
291
Chapter 54. Overview of Data Structures | Set 2 (Binary Tree, BST, Heap and Hash)
Space : O(n)
Search : O(1) [Average] O(n) [Worst case]
Insertion : O(1) [Average] O(n) [Worst Case]
Deletion : O(1) [Average] O(n) [Worst Case]
Hashing seems better than BST for all the operations. But in hashing, elements are un-
ordered and in BST elements are stored in an ordered manner. Also BST is easy to imple-
ment but hash functions can sometimes be very complex to generate. In BST, we can also
efficiently find floor and ceil of values.
Example : Hashing can be used to remove duplicates from a set of elements. Can also
be used find frequency of all items. For example, in web browsers, we can check visited
urls using hashing. In firewalls, we can use hashing to detect spam. We need to hash IP
addresses. Hashing can be used in any situation where want search() insert() and delete()
in O(1) time.
This article is contributed by Abhiraj Smit. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above.
Improved By : Rahul1421
Source
https://www.geeksforgeeks.org/overview-of-data-structures-set-2-binary-tree-bst-heap-and-hash/
292
Chapter 55
Print all elements in sorted order from row and column wise sorted matrix - GeeksforGeeks
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print
all elements of matrix in sorted order.
Example:
Output:
Elements of matrix in sorted order
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
We can use Young Tableau to solve the above problem. The idea is to consider given 2D
array as Young Tableau and call extract minimum O(N)
// A C++ program to Print all elements in sorted order from row and
// column wise sorted matrix
#include<iostream>
#include<climits>
using namespace std;
293
Chapter 55. Print all elements in sorted order from row and column wise sorted matrix
294
Chapter 55. Print all elements in sorted order from row and column wise sorted matrix
Output:
Time complexity of extract minimum is O(N) and it is called O(N2 ) times. Therefore the
overall time complexity is O(N3 ).
A better solution is to use the approach used for merging k sorted arrays. The idea is to
use a Min Heap of size N which stores elements of first column. The do extract minimum.
In extract minimum, replace the minimum element with the next element of the row from
which the element is extracted. Time complexity of this solution is O(N2 LogN).
#define N 4
295
Chapter 55. Print all elements in sorted order from row and column wise sorted matrix
{
MinHeapNode *harr; // pointer to array of elements in heap
int heap_size; // size of min heap
public:
// Constructor: creates a min heap of given size
MinHeap(MinHeapNode a[], int size);
296
Chapter 55. Print all elements in sorted order from row and column wise sorted matrix
297
Chapter 55. Print all elements in sorted order from row and column wise sorted matrix
Output:
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
Exercise:
Above solutions work for a square matrix. Extend the above solutions to work for an M*N
rectangular matrix.
This article is contributed by Varun. Please write comments if you find anything incorrect,
or you want to share more information about the topic discussed above
Source
https://www.geeksforgeeks.org/print-elements-sorted-order-row-column-wise-sorted-matrix/
298
Chapter 56
Input : x = 15
Output : 2 3 5 6 4
Input : x = 80
Output : 2 3 5 6 4 77 15 45
The idea is to do a preorder traversal of the give Binary heap. While doing preorder traversal,
if the value of a node is greater than the given value x, we return to the previous recursive
call. Because all children nodes in a min heap are greater than the parent node. Otherwise
we print current node and recur for its children.
299
Chapter 56. Print all nodes less than a value x in a Min Heap.
// Heap
#include<iostream>
using namespace std;
if (harr[pos] >= x)
{
/* Skip this node and its descendants,
as they are all >= x . */
return;
}
300
Chapter 56. Print all nodes less than a value x in a Min Heap.
printSmallerThan(x, left(pos));
printSmallerThan(x, right(pos));
}
301
Chapter 56. Print all nodes less than a value x in a Min Heap.
{
swap(harr[i], harr[smallest]);
MinHeapify(smallest);
}
}
return 0;
}
Output:
2 3 5 6 4 77 15 45 80
Source
https://www.geeksforgeeks.org/print-all-nodes-less-than-a-value-x-in-a-min-heap/
302
Chapter 57
def __str__(self):
return ' '.join([str(i) for i in self.queue])
303
Chapter 57. Priority Queue in Python
item = self.queue[max]
del self.queue[max]
return item
except IndexError:
print()
exit()
if __name__ == '__main__':
myQueue = PriorityQueue()
myQueue.insert(12)
myQueue.insert(1)
myQueue.insert(14)
myQueue.insert(7)
print(myQueue)
while not myQueue.isEmpty():
print(myQueue.delete())
Output:
12 1 14 7
14
12
7
1
()
Source
https://www.geeksforgeeks.org/priority-queue-in-python/
304
Chapter 58
pq.push(make_pair(10, 200));
pq.push(make_pair(20, 100));
pq.push(make_pair(15, 400));
Output :
305
Chapter 58. Priority queue of pairs in C++ (Ordered by first)
20 100
pq.push(make_pair(10, 200));
pq.push(make_pair(20, 100));
pq.push(make_pair(15, 400));
Output :
10 100
Source
https://www.geeksforgeeks.org/priority-queue-of-pairs-in-c-ordered-by-first/
306
Chapter 59
struct process {
processID,
burst time,
response time,
priority,
arrival time.
}
void quicksort(process array[], low, high)– This function is used to arrange the pro-
cesses in ascending order according to their arrival time.
int partition(process array[], int low, int high)– This function is used to partition the
array for sorting.
void insert(process Heap[], process value, int *heapsize, int *currentTime)– It
is used to include all the valid and eligible processes in the heap for execution. heapsize
defines the number of processes in execution depending on the current time currentTime
keeps record of the current CPU time.
void order(process Heap[], int *heapsize, int start)– It is used to reorder the heap
according to priority if the processes after insertion of new process.
void extractminimum(process Heap[], int *heapsize, int *currentTime)– This
function is used to find the process with highest priority from the heap. It also reorders the
heap after extracting the highest priority process.
void scheduling(process Heap[], process array[], int n, int *heapsize, int *cur-
rentTime)– This function is responsible for executing the highest priority extracted from
307
Chapter 59. Program for Preemptive Priority CPU Scheduling
Heap[].
void process(process array[], int n)– This function is responsible for managing the
entire execution of the processes as they arrive in the CPU according to their arrival time.
struct Process {
int processID;
int burstTime;
int tempburstTime;
int responsetime;
int arrivalTime;
int priority;
int outtime;
int intime;
};
308
Chapter 59. Program for Preemptive Priority CPU Scheduling
309
Chapter 59. Program for Preemptive Priority CPU Scheduling
return;
310
Chapter 59. Program for Preemptive Priority CPU Scheduling
// Driver code
int main()
{
int n, i;
Process a[5];
a[0].processID = 1;
a[0].arrivalTime = 4;
a[0].priority = 2;
a[0].burstTime = 6;
a[1].processID = 4;
a[1].arrivalTime = 5;
a[1].priority = 1;
a[1].burstTime = 3;
a[2].processID = 2;
a[2].arrivalTime = 5;
a[2].priority = 3;
a[3].burstTime = 7;
a[3].processID = 3;
a[3].arrivalTime = 1;
311
Chapter 59. Program for Preemptive Priority CPU Scheduling
a[3].priority = 4;
a[3].burstTime = 2;
a[4].processID = 5;
a[4].arrivalTime = 3;
a[4].priority = 5;
a[4].burstTime = 4;
priority(a, 5);
return 0;
}
Output:
The output displays the order in which the processes are executed in the memory and also
shows the average waiting time, average response time and average turn around time for
each process.
Source
https://www.geeksforgeeks.org/program-for-preemptive-priority-cpu-scheduling/
312
Chapter 60
313
Chapter 60. Python Code for time Complexity plot of Heap Sort
return 2 * i + 2
# heapSize = len(A)
# print("left", l, "Rightt", r, "Size", heapSize)
if l<= heapSize(A) and A[l] > A[i] :
largest = l
else:
largest = i
if r<= heapSize(A) and A[r] > A[largest]:
largest = r
if largest != i:
# print("Largest", largest)
A[i], A[largest]= A[largest], A[i]
# print("List", A)
MaxHeapify(A, largest)
314
Chapter 60. Python Code for time Complexity plot of Heap Sort
elements = list()
times = list()
for i in range(1, 10):
plt.xlabel('List Length')
plt.ylabel('Time Complexity')
plt.plot(elements, times, label ='Heap Sort')
plt.grid()
plt.legend()
plt.show()
# This code is contributed by Ashok Kajal
Output :
Source
https://www.geeksforgeeks.org/python-code-for-time-complexity-plot-of-heap-sort/
315
Chapter 61
We will use similar approach like K’th Smallest/Largest Element in Unsorted Array to solve
this problem.
def kthSmallest(input):
316
Chapter 61. Python heapq to find K’th smallest element in a 2D array
# Driver program
if __name__ == "__main__":
input = [[10, 25, 20, 40],
[15, 45, 35, 30],
[24, 29, 37, 48],
[32, 33, 39, 50]]
k = 7
kthSmallest(input)
Output:
Source
https://www.geeksforgeeks.org/python-heapq-find-kth-smallest-element-2d-array/
317
Chapter 62
Rearrange characters in a string such that no two adjacent are same - GeeksforGeeks
Given a string with repeated characters, task is rearrange characters in a string so that no
two adjacent characters are same.
Note : It may be assumed that the string has only lowercase English alphabets.
Examples:
Input: aaabc
Output: abaca
Input: aaabb
Output: ababa
Input: aa
Output: Not Possible
Input: aaaabc
Output: Not Possible
Prerequisite : priority_queue.
The idea is to put highest frequency character first (a greedy approach). We use a priority
queue (Or Binary Max Heap) and put all characters and ordered by their frequencies (highest
318
Chapter 62. Rearrange characters in a string such that no two adjacent are same
frequency character at root). We one by one take highest frequency character from the heap
and add it to result. After we add, we decrease frequency of the character and we temporarily
move this character out of priority queue so that it is not picked next time.
We have to follow the step to solve this problem, they are:
1. Build a Priority_queue or max_heap, pq that stores characters and their frequencies.
…… Priority_queue or max_heap is built on the bases of frequency of character.
2. Create a temporary Key that will used as the previous visited element ( previous element
in resultant string. Initialize it { char = ‘#’ , freq = ‘-1’ }
3. While pq is not empty.
….. Pop an element and add it to result.
….. Decrease frequency of the popped element by ‘1’
….. Push the previous element back into the priority_queue if it’s frequency > ‘0’
….. Make the current element as previous element for the next iteration.
4. If length of resultant string and original, print “not possible”. Else print result.
Below c++ implementation of above idea
struct Key
{
int freq; // store frequency of character
char ch;
319
Chapter 62. Rearrange characters in a string such that no two adjacent are same
// traverse queue
while (!pq.empty())
{
// pop top element from queue and add it
// to string.
Key k = pq.top();
pq.pop();
str = str + k.ch;
320
Chapter 62. Rearrange characters in a string such that no two adjacent are same
Output:
babab
Source
https://www.geeksforgeeks.org/rearrange-characters-string-no-two-adjacent/
321
Chapter 63
Skew Heap
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.
Example :
1. Consider the skew heap 1 to be
322
Chapter 63. Skew Heap
1. Let h1 and h2 be the two min skew heaps to be merged. Let h1’s root be smaller than
h2’s root (If not smaller, we can swap to get the same).
2. We swap h1->left and h1->right.
3. h1->left = merge(h2, h1->left)
Examples :
Let h1 be
10
/ \
20 30
323
Chapter 63. Skew Heap
/ /
40 50
Let h2 be
15
/ \
25 35
/ \
45 55
15
/ \
25 35
/ \
45 55
After recursive merge, we get (Please do it
using pen and paper).
15
/ \
30 25
/ \ \
35 40 45
324
Chapter 63. Skew Heap
// operations.
#include <bits/stdc++.h>
using namespace std;
struct SkewHeap
{
int key;
SkewHeap* right;
SkewHeap* left;
return h1;
}
325
Chapter 63. Skew Heap
// Driver Code
int main()
{
// Construct two heaps
SkewHeap heap, *temp1 = NULL,
*temp2 = NULL;
/*
5
/ \
/ \
10 12 */
int heap1[] = { 12, 5, 10 };
/*
3
/ \
/ \
7 8
/
/
14 */
int heap2[] = { 3, 7, 8, 14 };
326
Chapter 63. Skew Heap
Output:
Source
https://www.geeksforgeeks.org/skew-heap/
327
Chapter 64
Smallest Derangement of
Sequence
Input: 3
Output : 2 3 1
Explanation: The Sequence is 1 2 3.
Possible permutations are (1, 2, 3), (1, 3, 2),
(2, 1, 3), (2, 3, 1), (3, 1, 2) (3, 2, 1).
Derangements are (2, 3, 1), (3, 1, 2).
Smallest Derangement: (2, 3, 1)
Input : 5
Output : 2 1 4 5 3.
Explanation: Out of all the permutations of
(1, 2, 3, 4, 5), (2, 1, 4, 5, 3) is the first derangement.
Method 1:
We can modify the method shown in this article: Largest Derangement
Using a min heap we can successively get the least element and place them in more significant
positions, taking care that the property of derangement is maintained.
Complexity: O(N * log N)
328
Chapter 64. Smallest Derangement of Sequence
void generate_derangement(int N)
{
// Generate Sequence and insert into a
// priority queue.
int S[N + 1];
priority_queue<int, vector<int>, greater<int> > PQ;
for (int i = 1; i <= N; i++) {
S[i] = i;
PQ.push(S[i]);
}
if (D[N] == S[N])
swap(S[N], D[N]);
// Print Derangement
for (int i = 1; i <= N; i++)
printf("%d ", D[i]);
printf("\n");
}
// Driver code
int main()
{
generate_derangement(10);
return 0;
}
329
Chapter 64. Smallest Derangement of Sequence
Output:
2 1 4 3 6 5 8 7 10 9
Method 2
Since we are given a very specific sequence i.e we can cal-
culate the answer even more efficiently.
Divide the original sequence into pairs of two elements, and then swap the elements of each
pair.
If N is odd then the last pair needs to be swapped again.
Pictorial Representation
330
Chapter 64. Smallest Derangement of Sequence
331
Chapter 64. Smallest Derangement of Sequence
void generate_derangement(int N)
{
// Generate Sequence S
int S[N + 1];
for (int i = 1; i <= N; i++)
S[i] = i;
// Generate Derangement
int D[N + 1];
for (int i = 1; i <= N; i += 2) {
if (i == N) {
// Only if i is odd
// Swap S[N-1] and S[N]
D[N] = S[N - 1];
D[N - 1] = S[N];
}
else {
D[i] = i + 1;
D[i + 1] = i;
}
}
// Print Derangement
for (int i = 1; i <= N; i++)
printf("%d ", D[i]);
printf("\n");
}
// Driver Program
int main()
{
generate_derangement(10);
return 0;
}
Output:
2 1 4 3 6 5 8 7 10 9
Note : The auxiliary space can be reduced to O(1) if we perform the swapping operations
on S itself.
332
Chapter 64. Smallest Derangement of Sequence
Source
https://www.geeksforgeeks.org/smallest-derangement-sequence/
333
Chapter 65
We can use Insertion Sort to sort the elements efficiently. Following is the C code for
standard Insertion Sort.
334
Chapter 65. Sort a nearly sorted (or K sorted) array
The inner loop will run at most k times. To move every element to its correct place, at most
k elements need to be moved. So overall complexity will be O(nk)
We can sort such arrays more efficiently with the help of Heap data structure.
Following is the detailed process that uses Heap.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See
this GFact)
2) One by one remove min element from heap, put it in result array, and add a new element
to heap from remaining elements.
Removing an element and adding a new element to min heap will take Logk time. So overall
complexity will be O(k) + O((n-k)*logK)
C++
335
Chapter 65. Sort a nearly sorted (or K sorted) array
arr[index++] = pq.top();
pq.pop();
}
}
return 0;
}
#include<iostream>
using namespace std;
336
Chapter 65. Sort a nearly sorted (or K sorted) array
// to remove min (or root), add a new value x, and return old root
int replaceMin(int x);
// Given an array of size n, where every element is k away from its target
// position, sorts the array in O(nLogk) time.
int sortK(int arr[], int n, int k)
{
// Create a Min Heap of first (k+1) elements from
// input array
int *harr = new int[k+1];
for (int i = 0; i<=k && i<n; i++) // i < n condition is needed when k > n
harr[i] = arr[i];
MinHeap hp(harr, k+1);
// FOLLOWING ARE IMPLEMENTATIONS OF STANDARD MIN HEAP METHODS FROM CORMEN BOOK
// Constructor: Builds a heap from a given array a[] of given size
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2;
337
Chapter 65. Sort a nearly sorted (or K sorted) array
while (i >= 0)
{
MinHeapify(i);
i--;
}
}
// Method to change root with given value x, and return the old root
int MinHeap::replaceMin(int x)
{
int root = harr[0];
harr[0] = x;
if (root < x)
MinHeapify(0);
return root;
}
338
Chapter 65. Sort a nearly sorted (or K sorted) array
return 0;
}
Output:
The Min Heap based method takes O(nLogk) time and uses O(k) auxiliary space.
We can also use a Balanced Binary Search Tree instead of Heap to store K+1 elements.
The insertand deleteoperations on Balanced BST also take O(Logk) time. So Balanced BST
based method will also take O(nLogk) time, but the Heap bassed method seems to be more
efficient as the minimum element will always be at root. Also, Heap doesn’t need extra
space for left and right pointers.
Source
https://www.geeksforgeeks.org/nearly-sorted-algorithm/
339
Chapter 66
A simple solution is to sort the array using any standard sorting algorithm. The time
complexity of this solution is O(n Log n)
A better solution is to use priority queue (or heap data structure).
We have discussed a simple implementation in Sort a nearly sorted (or K sorted) array. In
this post, an STL based implementation is done.
340
Chapter 66. Sort a nearly sorted array using STL
341
Chapter 66. Sort a nearly sorted array using STL
return 0;
}
Output:
Source
https://www.geeksforgeeks.org/sort-a-nearly-sorted-array-using-stl/
342
Chapter 67
Example:
Machine M1 contains 3 numbers: {30, 40, 50}
Machine M2 contains 2 numbers: {35, 45}
Machine M3 contains 5 numbers: {10, 60, 70, 80, 100}
Output: {10, 30, 35, 40, 45, 50, 60, 70, 80, 100}
// A program to take numbers from different machines and print them in sorted order
343
Chapter 67. Sort numbers stored on different machines
#include <stdio.h>
344
Chapter 67. Sort numbers stored on different machines
345
Chapter 67. Sort numbers stored on different machines
n = minHeap->count - 1;
for( i = (n - 1) / 2; i >= 0; --i )
minHeapify( minHeap, i );
}
buildMinHeap( minHeap );
}
minHeapify( minHeap, 0 );
return temp.head;
}
346
Chapter 67. Sort numbers stored on different machines
{
ListNode* temp = extractMin( minHeap );
printf( "%d ",temp->data );
}
}
return 0;
}
Output:
10 30 35 40 45 50 60 70 80 100
Source
https://www.geeksforgeeks.org/sort-numbers-stored-on-different-machines/
347
Chapter 68
Sum of all elements between k1’th and k2’th smallest elements - GeeksforGeeks
Given an array of integers and two numbers k1 and k2. Find sum of all elements between
given two k1’th and k2’th smallest elements of array. It may be assumed that (1 <= k1 <
k2 <= n) and all elements of array are distinct.
Examples :
Method 1 (Sorting)
First sort the given array using a O(n log n) sorting algorithm like Merge Sort, Heap Sort,
etc and return the sum of all element between index k1 and k2 in the sorted array.
Below is the implementation of the above idea :
C++
348
Chapter 68. Sum of all elements between k1’th and k2’th smallest elements
#include <bits/stdc++.h>
// Driver program
int main()
{
int arr[] = { 20, 8, 22, 4, 12, 10, 14 };
int k1 = 3, k2 = 6;
int n = sizeof(arr) / sizeof(arr[0]);
cout << sumBetweenTwoKth(arr, n, k1, k2);
return 0;
}
Java
class GFG {
349
Chapter 68. Sum of all elements between k1’th and k2’th smallest elements
result += arr[i];
return result;
}
// Driver code
public static void main(String[] args)
{
System.out.print(sumBetweenTwoKth(arr,
k1, k2));
}
}
Python3
result = 0
for i in range(k1, k2-1):
result += arr[i]
return result
# Driver code
arr = [ 20, 8, 22, 4, 12, 10, 14 ]
k1 = 3; k2 = 6
n = len(arr)
print(sumBetweenTwoKth(arr, n, k1, k2))
C#
350
Chapter 68. Sum of all elements between k1’th and k2’th smallest elements
class GFG {
return result;
}
// Driver code
public static void Main()
{
int[] arr = {20, 8, 22, 4, 12, 10, 14};
int k1 = 3, k2 = 6;
int n = arr.Length;
Output:
26
351
Chapter 68. Sum of all elements between k1’th and k2’th smallest elements
3) Do extract minimum k2 – k1 – 1 times and sum all extracted elements. (This step takes
O ((K2 – k1) * Log n) time)
Overall time complexity of this method is O(n + k2 Log n) which is better than sorting
based method.
Improved By : nitin mittal, AbhishekVats3
Source
https://www.geeksforgeeks.org/sum-elements-k1th-k2th-smallest-elements/
352
Chapter 69
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
A quick look over the above algorithm suggests that the running time is ,
.
For finding the Time Complexity of building a heap, we must know the number of nodes
having height h.
353
Chapter 69. Time Complexity of building a heap
For this we use the fact that, A heap of size n has at most nodes with height h.
Now to derive the time complexity, we express the total cost of Build-Heap as-
(1)
Step 2 uses the properties of the Big-Oh notation to ignore the ceiling function and the con-
(2)
On differentiating both sides and multiplying by x, we get
(3)
Putting the result obtained in (3) back in our derivation (1), we get
354
Chapter 69. Time Complexity of building a heap
(4)
Hence Proved that the Time complexity for Building a Binary Heap is .
Reference :
http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf
Source
https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/
355
Chapter 70
356
Chapter 70. Tournament Tree (Winner Tree) and Binary Heap
The above tree contains 4 leaf nodes that represent players and have 3 levels 0, 1 and 2.
Initially 2 games are conducted at level 2, one between 5 and 3 and another one between
7 and 8. In the next move, one more game is conducted between 5 and 8 to conclude the
final winner. Overall we need 3 comparisons. For second best player we need to trace the
candidates participated with final winner, that leads to 7 as second best.
Median of Sorted Arrays
Tournament tree can effectively be used to find median of sorted arrays. Assume, given
M sorted arrays of equal size L (for simplicity). We can attach all these sorted arrays to
the tournament tree, one array per leaf. We need a tree of height CEIL (log2 M) to have
atleast M external nodes.
Consider an example. Given 3 (M = 3) sorted integer arrays of maximum size 5 elements.
What should be the height of tournament tree? We need to construct a tournament tree
of height log2 3 .= 1.585 = 2 rounded to next integer. A binary tree of height 2 will have 4
leaves to which we can attach the arrays as shown in the below figure.
357
Chapter 70. Tournament Tree (Winner Tree) and Binary Heap
We can observe that the winner is from Array2. Hence the next element from Array2 will
dive-in and games will be played along the winner path of previous tournament.
Note that infinity is used as sentinel element. Based on data being hold in nodes we can select
the sentinel character. For example we usually store the pointers in nodes rather than keys,
so NULL can serve as sentinel. If any of the array exhausts we will fill the corresponding
leaf and upcoming internal nodes with sentinel.
After the second tournament, the tree appears as below,
The next winner is from Array1, so next element of Array1 array which is 5 will dive-in to
the next round, and next tournament played along the path of 2.
The tournaments can be continued till we get median element which is (5+3+5)/2 = 7th
element. Note that there are even better algorithms for finding median of union of sorted
arrays, for details see the related links given below.
358
Chapter 70. Tournament Tree (Winner Tree) and Binary Heap
Source
https://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
359
Chapter 71
Source
https://www.geeksforgeeks.org/where-is-heap-sort-used-practically/
360
Chapter 72
Why is Binary Heap Preferred over BST for Priority Queue? - GeeksforGeeks
A typical Priority Queue requires following operations to be efficient.
1. O(1)
2. O(Logn)
3. O(Logn)
4. O(Logn)
361
Chapter 72. Why is Binary Heap Preferred over BST for Priority Queue?
A Self Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc can also support
above operations with same time complexities.
1. Finding minimum and maximum are not naturally O(1), but can be easily imple-
mented in O(1) by keeping an extra pointer to minimum or maximum and updating
the pointer with insertion and deletion if required. With deletion we can update by
finding inorder predecessor or successor.
2. Inserting an element is naturally O(Logn)
3. Removing maximum or minimum are also O(Logn)
4. Decrease key can be done in O(Logn) by doing a deletion followed by insertion. See
this for details.
• Since Binary Heap is implemented using arrays, there is always better locality of
reference and operations are more cache friendly.
• Although operations are of same time complexity, constants in Binary Search Tree are
higher.
• We can build a Binary Heap in O(n) time. Self Balancing BSTs require O(nLogn)
time to construct.
• Binary Heap doesn’t require extra space for pointers.
• Binary Heap is easier to implement.
• There are variations of Binary Heap like Fibonacci Heap that can support insert and
decrease-key in Θ(1) time
This article is contributed by Vivek Gupta. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Source
https://www.geeksforgeeks.org/why-is-binary-heap-preferred-over-bst-for-priority-queue/
362
Chapter 73
heapq in Python to print all elements in sorted order from row and column wise sorted
matrix - GeeksforGeeks
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print
all elements of matrix in sorted order.
Examples:
This problem has existing solution please refer link. We will solve this problem in python
with the same approach of merging two sorted arrays using heapq module.
363
Chapter 73. heapq in Python to print all elements in sorted order from row and column
wise sorted matrix
def sortedMatrix(mat):
return result
if __name__ == "__main__":
mat = [[10, 20, 30, 40],[15, 25, 35, 45], \
[27, 29, 37, 48],[32, 33, 39, 50]]
print 'Elements of matrix in sorted order'
print sortedMatrix(mat)
Output:
Source
https://www.geeksforgeeks.org/heapq-python-print-elements-sorted-order-row-column-wise-sorted-matrix/
364
Chapter 74
365
Chapter 74. k largest(or smallest) elements in an array | added Min Heap method
C++
// driver program
int main()
{
int arr[] = {1, 23, 12, 9, 30, 2, 50};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
kLargest(arr, n, k);
}
Java
class GFG
{
public static void kLargest(Integer [] arr, int k)
{
// Sort the given array arr in reverse order
// This method doesn't work with primitive data
// types. So, instead of int, Integer type
// array will be used
366
Chapter 74. k largest(or smallest) elements in an array | added Min Heap method
Arrays.sort(arr, Collections.reverseOrder());
Python
# Driver program
arr = [1, 23, 12, 9, 30, 2, 50]
#n = len(arr)
k = 3
kLargest(arr, k)
Output:
50 30 23
367
Chapter 74. k largest(or smallest) elements in an array | added Min Heap method
Source
https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
368
Chapter 75
Template :
void make_heap (RandomAccessIterator first, RandomAccessIterator last);
Parameters :
first : The pointer to the starting element of sequence that has to
be transformed into heap.
last : The pointer to the next address to last element of sequence that
has to be transformed into heap.
#include<iostream>
#include<algorithm> // for heap
#include<vector>
using namespace std;
int main()
369
Chapter 75. std::make_heap() in C++ STL
{
// initializing vector;
vector<int> vi = { 4, 6, 7, 9, 11, 4 };
Output:
Template :
void make_heap (RandomAccessIterator first, RandomAccessIterator last, comp);
Parameters :
first : The pointer to the starting element of sequence that has to
be transformed into heap.
last : The pointer to the next address to last element of sequence that
has to be transformed into heap.
comp : The comparator function that returns a boolean
true/false of the each elements compared. This function
accepts two arguments. This can be function pointer or
function object and cannot change values.
#include<iostream>
#include<algorithm> // for heap
#include<vector>
using namespace std;
370
Chapter 75. std::make_heap() in C++ STL
int main()
{
// initializing vector;
vector<int> vi = { 15, 6, 7, 9, 11, 45 };
Output:
#include<iostream>
#include<algorithm> // for heap
#include<vector>
using namespace std;
int main()
{
// initializing vector;
// initial job priorities
vector<int> vi = { 15, 6, 7, 9, 11, 19};
371
Chapter 75. std::make_heap() in C++ STL
Output:
Source
https://www.geeksforgeeks.org/stdmake_heap-c-stl/
372