What is a Heap?                            

A heap is a special Tree-based data structure in which the tree is a complete Binary Tree in which each level has all of its nodes. A complete binary tree is a tree in which each node can have a max of two children, and all the levels should be filled except for the last level, where nodes should be filled from left to right.

Min Heap: The value at each node should be smaller than its children.               

Max Heap: The value at each node should be greater than its children.                     

We can implement a heap as an array.                       

• The root node, i = 0 is the first item of the array                              
• A parent node, parent(i) = (i-1) / 2                            
• A left child node, left(i) = 2i + 1                                
• A right child node, right(i) = 2i + 2                            

Implementation                                                                                                    

def get_left_child(i):                                                         
    return 2 * i + 1                                                             

def get_right_child(i):                                                      
    return 2 * i + 2                                                           

def min_heapify(arr, i):                                                 
    left = get_left_child(i)                                                   
    right = get_right_child(i)                                             
    smallest = i                                                                

    if left < len(arr) and arr[i] > arr[left]:                           
        smallest = left                                                          
    if right < len(arr) and arr[smallest] > arr[right]:                     
        smallest = right                                                            
    if smallest != i:                                                                    
        arr[i], arr[smallest] = arr[smallest], arr[i]                            
        min_heapify(arr, smallest)                                                    

def build_min_heap(arr):                                                         
    for i in reversed(range(len(arr)//2)):                                                     
        min_heapify(arr, i)                                                                     

def max_heapify(arr, i):                                                                   
    left = get_left_child(i)                                                                   
    right = get_right_child(i)                                                           
    largest = i                                                                                

    if left < len(arr) and arr[left] > arr[largest]:                                      
        largest = left                                                           
    if right < len(arr) and arr[right] > arr[largest]:                       
        largest = right                                                                 
    if largest != i:                                                                                
        arr[i], arr[largest] = arr[largest], arr[i]                                                      
        max_heapify(arr, largest)                                                                        
 

Operation	Average	Worst Case	Best Case
Search	O(n)	O(n)	O(1)
Insert	O(1)	O(log n)	O(1)
Delete	O(log n)	O(log n)	O(1)
Peek	O(1)	O(1)	O(1)

Applications of Heap                                                                   

A heap tree can be used for many different purposes, including the following:

• Djikstra's Algorithm is used to find the shortest path between two nodes in a graph.
• Heap Sort algorithm. Heap Sort is used in systems concerned with security and embedded systems, such as the Linux Kernel.
• Implementing priority queues.
• Finding the smallest or largest element in an array, (a min-heap tree and max-heap tree would be used, respectively).
• Heap is used in the construction of priority queue. We can insert, delete, identify the highest priority element, or insert and extract with priority, among other things, in O(log N) time using a priority queue.  Priority queues themselves have more advanced uses, such as bandwidth control in an n/w router, prims and Dijkstra's algorithm, Huffman coding, and the BFS algorithm. 
• Hidden Markov Model (HMM) is especially known for its application in pattern recognition (speech, handwriting, gesture recognition) using the heap.

heapq in Python                                          

In Python, it is available using the “heapq” module. The property of this data structure in Python is that each time the smallest heap element is popped(min-heap). The heap[0] element also returns the smallest element each time. 

Below is a list of these functions.                                                    

• heappush(heap, ele): This function is used to insert the element mentioned in its arguments into a heap. The order is adjusted, so that heap structure is maintained.
• heappop(heap): This function is used to remove and return the smallest element from the heap. The order is adjusted, so that heap structure is maintained.
• heappushpop(heap, ele):- This function combines the functioning of both push and pop operations in one statement, increasing efficiency. Heap order is maintained after this operation.
• heapreplace(heap, ele):- This function also inserts and pops elements in one statement, but it is different from the above function. In this, the element is first popped, then the element is pushed. i.e, the value larger than the pushed value can be returned. heapreplace() returns the smallest value originally in the heap regardless of the pushed element as opposed to heappushpop().
• nlargest(k, iterable, key = fun): This function is used to return the k largest elements from the iterable specified and satisfy the key if mentioned.
• nsmallest(k, iterable, key = fun): This function is used to return the k smallest elements from the iterable specified and satisfy the key if mentioned.

 

LeetCode 295 - Find Median from Data Stream [hard]

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:                                         

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

To be able to solve these kinds of problems, we want to know the smallest element in one part and the biggest element in the other part. Two Heaps pattern uses two Heap data structure to solve these problems; a  Min heap to find the smallest element and a Max Heap to find the biggest element.

Solution:                                                                                      

from heapq import heappush, heappop                                  
class MedianFinder:                                                                

    def __init__(self):                                                                
        self.max_heap = []                                                          
        self.min_heap = []                                                             

    def addNum(self, num: int) -> None:                            
        if not self.max_heap or -self.max_heap[0] >= num:
            heappush(self.max_heap, -num)                           
        else:                                                                            
            heappush(self.min_heap, num)                                
        if len(self.max_heap) > len(self.min_heap) + 1:
            heappush(self.min_heap, -heappop(self.max_heap))      
        elif len(self.max_heap) < len(self.min_heap):
            heappush(self.max_heap, -heappop(self.min_heap))     

    def findMedian(self) -> float:                                                      
        if len(self.max_heap) == len(self.min_heap):                         
            return (-self.max_heap[0] + self.min_heap[0] )/ 2.0            
        return -float(self.max_heap[0])                                                  

Time Complexity: O(log N) for addNum() and O(1) for  findMedian().   Space Complexity: O(N)

 

LeetCode 502. IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Solution:                                                                                       

import heapq                                                                                        
class Solution:                                                                                     
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        heap = []                                                                                          
        for c,p in zip(capital, profits):                                                                
            heapq.heappush(heap, (c,-p))                                                    
        do_list = []                                                                            
        for i in range(k):                                                                          
            while heap and heap[0][0] <= w:                                            
                c,p = heapq.heappop(heap)                                                    
                heapq.heappush(do_list, (p,c))                            
            if do_list:                                                                      
                p,c = heapq.heappop(do_list)                                      
                w += -1 * p                                                                          
        return w