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