Heap Problem Set

1,2,3,5,7,12,14, 19/20, 21, 22, **23, **25
Heap is the underlying implementation of Priority Queue. We use Priority Queue classes to implement min and max heaps in Java. SO
1 Index array for heap –
Parent = i/2
Child = 2*i , 2*i + 1
Last Non-Leaf Node = floor(n/2)
Leaf Node Starts from = floor(n/2 + 1)

Min Heap Visualizer  Max Heap Visualizer Heap Basics Question List
Heap is an almost complete binary tree.
Time complexity of building a heap = O(n) (and not O(n(logn))) – SO
N – 1 internal nodes in a binary tree with N leaf (external) nodes GFG
In a (1-indexed)array leave nodes are from floor((n/2) + 1).
The last internal node is present at index (2n-2)/2 assuming that indexing begins with 0.

It would be O(n log n) if you built the heap by repeatedly inserting elements. However, you can create a new heap more efficiently by inserting the elements in arbitrary order and then applying an algorithm to “heapify” them into the proper order (depending on the type of heap of course). SO

  1. ***** Min Heap – Insert and Extract All Min Element. Code. Article 

  2. ***** Max Heap – Insert and Extract All Max ElementCode 

  3. ***** Given two binary max heaps as arrays, merge the given heaps. GFG 
     Algo: 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. The complexity of merging the heaps is equal to O(n + m). Code


  4. *** Find the largest/maximum element in a Min Heap.  
    Algo: In a min heap the largest element will be in any one of the leaf node. So if we find the start of the leaf node, we can iterate through all the leaf nodes and find the largest one. How to find the index of the first leaf node ?? We can get the index of the last root element. The element next to it will be the starting of the lead nodes since all the leaf nodes are arranged linearly in the array.
    In a (1-indexed)array leave nodes are from floor((n/2)+1).


  5. **** K largest element in a stream of numbers. Code  GFG
    Algo: Maintain a Min Heap of size k. Insert the first k elements in the heap. For elements after first k elements, check if the minimum in the heap, is smaller than the incoming element then remove the minimum and insert the new incoming element. At any given time, there will be the first k largest element in the heap.


  6. Why in a heap implemented by array the index 0 is left unused? SO
    root is element 0; children of element n are elements 2n+1 and 2n+2;
    root is element 1; children of element n are elements 2n and 2n+1.
    On most computers, the LEFT procedure can compute 2*i in one instruction by simply shifting the binary representation of i left by one bit position. Similarly, the RIGHT procedure can quickly compute 2*i+1 by shifting the binary representation of i left by one bit position and then adding in a 1 as the low-order bit. The PARENT procedure can compute i/2 by shifting i right one bit position.


  7. ***** Median in a stream of integers (running integers)  Article  YouTube  Code             OR
    Numbers are randomly generated and stored into an (expanding) array. How would you keep track of the median ?
    Time Complexity: If we omit the way how stream was read, complexity of median finding is O(N log N).
    Algo: Maintain two heap – left(max heap) and right(min heap). The idea is to keep both the heap balanced such that all element above a certain element(in this case first element) all elements will be  on the right side(min heap) and all smaller will be on left side(max heap). We always keep the elements distributed such that the difference in size is atmost 1. So whenever we need median, if total element count is odd we take the peak element from max-heap. When the element count is even we take the peak element from max and min heap and return their average.


  8. *** Given a set of 1 Trillion integers on hard disk, find the smallest 1 million of them. You can fit at most 1 million integers in memory at a time.  Link
    Expected – O(n log m), n = all the numbers, m = the size of the set of numbers you want to find.
    Algo: You can do this efficiently in O(n log m) by using a heap. ( n = all the numbers, m = the size of the set of numbers you want to find ).Go through the trillion numbers one at a time. For each new number do one of the following.

    1. If the heap has < 1 million nodes insert the new number into the heap.
    2. If the heap has exactly 1 million nodes and the top node is > than the new number, then pop the top node from the heap, and insert a node with the new number.
    3. If neither 1 or 2 are true then toss the number.

    After you go through all the trillion entries then the resulting heap will have the 1 million smallest numbers. Inserting and deleting from the heap is O(log m). The single pass through the heap is n. So, the algorithm is n*log (m)


  9. Largest triplet product in a stream – Given a stream of integers represented as arr[]. For each index i from 0 to n-1, print the multiplication of largest, second largest, third largest element of the subarray arr[0…i]. If i < 2 print -1.
    Algo: Same as Q5 on this page( K largest element in a stream of numbers). Maintain a Min Heap.


  10. Given an array of n numbers and a positive integer k. The problem is to find k numbers with most occurrences, i.e., the top k numbers having the maximum frequency. If two numbers have same frequency then the larger number should be given preference.  GFG
    Algo:
    1. Using hash table, we create a frequency table which stores the frequency of occurrence of each number in the given array. In the hash table we define (x, y) tuple, where x is the key(number) and y is its frequency in the array. Now we traverse this hash table and create an array freq_arr[] which stores these (number, frequency) tuples. Sort this freq_arr[] on the basis of the conditions defined in the problem statement. Now, print the first k numbers of this freq_arr[].
    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.
    Comparator Example 2


  11. **** K’th Smallest/Largest Element in Unsorted Array. GFS.  /
    k largest(or smallest) elements in an array
    Algo:
    1. Maintain a Min/Max heap accordingly. Then extract the min/max k number of times.  Time complexity of this solution is O(n + kLogn).2. We can also use quick select for the same. It has a better average performance.  GFG


  12. **** Implement stack using priority queue or heap. GFG. Code
    Code with different Comparator implementation
    Algo: Stack is a LIFO DS. So suppose we choose max heap to implement a stack. We need some way to recognize the priority, which will push the last inserted element on the top of the heap. One way we could do is to push the timestamp. So for every new element pushed the timestamp will be higher then the previous pushed value. The code below uses the same logic, just that instead of timestamp, we use a counter variable.


  13. Given the level order traversal of a Complete Binary Tree, determine whether the Binary Tree is a valid Min-Heap. GFG
    Algo: 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.
    We only need to check non-leaf node.
    In a (1-indexed)array leave nodes are from floor((n/2) + 1).
    So we need to check from floor(n/2) down to 1 using the formula 2*i and 2*i+1. Above formula is for a 0 based array.
    O(n) complexity worst case complexity.


  14. Check if a given Binary Tree is Heap. GFG. Code
    Algo: Do a level order traversal and keep checking the each node satisfies the max heap property and that all nodes are as left as possible. We check for node value before pushing the node data to queue.


  15. How to check if a given array represents a Binary Heap? GFG
    Algo: Check all internal nodes. See the formula above.
    The last internal node is present at index (n-2)/2 assuming that indexing begins with 0.
    In a (1-indexed)array leave nodes are from floor((n/2) + 1)


  16. **** Rearrange characters in a string such that no two adjacent are same.
    GFG Code 
    Algo: We determine the frequency of each char in the input string. Then we add these to a priority queue. We want to get element based on frequency so need to use custom comparator. So we basically add object which holds the char and there frequency. Now we poll the element and the element with maximum element is returned and we add this char to out o/p string( we don’t add it back to the queue now). We first poll the next object and the element with next higher frequency is returned. We add this element to the o/p string and add the previous object (with decreased frequency). So what this does is that we don’t get highest frequency element at once by are alternated. If we get an element with count 0, we break. Check code for a more.


  17. *** Sum of all elements between k1’th and k2’th smallest elements. GFG
    Algo:
    1.
     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.
    2. Create a min heap –
    1) Create a min heap of all array elements. (This step takes O(n) time)
    2) Do extract minimum k1 times (This step takes O(K1 Log n) time)
    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.


  18. Minimum sum of two numbers formed from digits of an array. GFG
    Algo:
    – Maintain a min heap. Poll two digits at a time and that each digit to the two numbers until the heap is empty. O(n) to build the heap and then nLog(n) to get those number.
    – Sorting the element is also a solution but that takes, nlog(n) time.


  19. *** Print all elements in sorted order from row and column wise sorted matrix. GFG Code Based on this SO logic
    Time complexity of this solution is O(N2LogN)


  20. *** Kth smallest element in a row-wise and column-wise sorted 2D array GFG
    Code  Based on this SO logic  This is a better implementation


  21. *** Given a book of words. Assume you have enough main memory to accommodate all words. design a data structure to find top K maximum occurring words. The data structure should be dynamic so that new words can be added. GFG

  22. ** There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost. GFG
    Algo: 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.
    3) Return the value of only left item in min heap.


  23. *** Merge k sorted arrays. GFG Code
    Algo:
    Using Min Heap:
    We can merge arrays in O(nk*Logk) time using Min Heap.
    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 a the heap
    3. Repeat following steps n*k times.
    a) Get minimum element from heap (minimum is always at root) and store it in output array.
    b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.You should note that when we say complexity is O(n log k), we assume that n means TOTAL number of elements in ALL of k arrays, i.e. number of elements in a final merged array. For example, if you want to merge k arrays that contain n elements each, total number of elements in final array will be nk. So complexity will be O(nk log k) SO  Note that at any point of time there will be only k pointers in the min-heap.
    This logic is same as when we need to sort an row and column wise sorted matrix (Q19/20 – SO)
    Similar Concept: Merge k sorted Linked List. GFG
    Similar:  
    Given N machines. Each machine contains some numbers in sorted form. But the amount of numbers, each machine has is not fixed. Output the numbers from all the machine in sorted non-decreasing form. GFG

  24. *** Design an efficient data structure for given operations….check full question on GFG
    Logic:
    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.


  25. *** Sort a nearly sorted (or K sorted) array GFG
    Algo:
    1. Insertion Sort. O(nk)
    2.  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
    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)


  26. External Sorting – One example of external sorting is the external merge sort algorithm, which sorts chunks that each fit in RAM, then merges the sorted chunks together. We first divide the file into runs such that the size of a run is small enough to fit into main memory. Then sort each run in main memory using merge sort sorting algorithm. Finally merge the resulting runs together into successively bigger runs, until the file is sorted.
    This logic is based on merging k sorted array using min-heap.


  27. [Pending] Heap with delete key and change node value implementation

  28. [Pending] Convert Max Heap to Min Heap

  29. [Pending] Convert Min Heap to Max Heap – In Linear Time

  30. [Pending] Convert a binary heap to a Binary Search Tree.

  31. **** In-place Convert BST into a Min-HeapGFG
    1.If we are allowed to use extra space, we can perform in-order traversal of the tree and store the keys in an auxiliary array. As we’re doing in-order traversal on a BST, array will be sorted. Finally, we construct a complete binary tree from the sorted array by level order traversal and from left to right by taking next minimum element from sorted array. The constructed binary tree will be a min-Heap. This solution works in O(n) time, but is not in-place.
    2. The idea is to convert the binary search tree into a sorted linked list first. Finally we convert the sorted linked list into a min-Heap by setting the left and right pointers appropriately. We can do this by doing a Level order traversal of the partially built Min-Heap Tree using queue and traversing the linked list at the same time.
    Similar: If we need to create a max heap, do a reverse inorder traversal. This will create an array/ linked list in descending order. Then do a level order traversal.


  32. Given a complete binary search tree. The problem is to convert the given BST into a Min Heap with the condition that all the values in the left subtree of a node should be less than all the values in the right subtree of the node. This condition is applied on all the nodes in the so converted Min Heap. GFG
    Algo: 
    Create an array arr[] of size n ( n = nodes in tree). Perform the inorder traversal of the BST and copy the node values in the arr. Now perform the preorder traversal of the tree. While traversing the root during the preorder traversal, one by one copy the values from the array arr[] to the nodes.   



  33. K-ary Heap. GFG – Good to know
  34. Delete from heap. SO
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s