<reponame>gyan42/interview-preparation-qns
"""

Heap is a special tree structure in which each parent node is less than or equal to its child node.
Then it is called a Min Heap. If each parent node is greater than or equal to its child node then it is called a max heap.


MinHeap operations

    Insertion O(logn)O(log n)O(logn): Finding the exact position of the new element is performed in lognlog nlogn since it is only compared with the position of the parent nodes.
    Delete Min O(logn)O(log n)O(logn): After the minimum element is removed, the heap has to put the new root in place.
    Find Min O(1)O(1)O(1): This is possible because the heap data structure always has the minimum element on the root node.
    Heapify O(n)O(n)O(n): This operation rearranges all the nodes after deletion or insertion operation. The cost of this operation is nnn since all the elements have to be moved to keep the heap properties.
    Delete O(logn)O(log n)O(logn): A specific element from the heap can be removed in lognlog nlogn time.

"""

"""
Min Heap Implementation in Python

            5                      13
         /      \               /       \  
       10        15           16         31 
      /                      /  \        /  \
    30                     41    51    100   41
    
"""


class MinHeap:
    def __init__(self):
        """
        On this implementation the heap list is initialized with a value
        """
        self.heap_list = [0]
        self.current_size = 0

    def sift_up(self, i):
        """
        Moves the value up in the tree to maintain the heap property.
        """
        # While the element is not the root or the left element
        while i // 2 > 0:
            # If the element is less than its parent swap the elements
            if self.heap_list[i] < self.heap_list[i // 2]:
                self.heap_list[i], self.heap_list[i // 2] = self.heap_list[i // 2], self.heap_list[i]
            # Move the index to the parent to keep the properties
            i = i // 2

    def insert(self, k):
        """
        Inserts a value into the heap
        """
        # Append the element to the heap
        self.heap_list.append(k)
        # Increase the size of the heap.
        self.current_size += 1
        # Move the element to its position from bottom to the top
        self.sift_up(self.current_size)

    def sift_down(self, i):
        # if the current node has at least one child
        while (i * 2) <= self.current_size:
            # Get the index of the min child of the current node
            mc = self.min_child(i)
            # Swap the values of the current element is greater than its min child
            if self.heap_list[i] > self.heap_list[mc]:
                self.heap_list[i], self.heap_list[mc] = self.heap_list[mc], self.heap_list[i]
            i = mc

    def min_child(self, i):
        # If the current node has only one child, return the index of the unique child
        if (i * 2) + 1 > self.current_size:
            return i * 2
        else:
            # Herein the current node has two children
            # Return the index of the min child according to their values
            if self.heap_list[i * 2] < self.heap_list[(i * 2) + 1]:
                return i * 2
            else:
                return (i * 2) + 1

    def delete_min(self):
        # Equal to 1 since the heap list was initialized with a value
        if len(self.heap_list) == 1:
            return 'Empty heap'

        # Get root of the heap (The min value of the heap)
        root = self.heap_list[1]

        # Move the last value of the heap to the root
        self.heap_list[1] = self.heap_list[self.current_size]

        # Pop the last value since a copy was set on the root
        *self.heap_list, _ = self.heap_list

        # Decrease the size of the heap
        self.current_size -= 1

        # Move down the root (value at index 1) to keep the heap property
        self.sift_down(1)

        # Return the min value of the heap
        return root


"""
Driver program
"""
# Same tree as above example.
my_heap = MinHeap()
my_heap.insert(5)
my_heap.insert(6)
my_heap.insert(7)
my_heap.insert(9)
my_heap.insert(13)
my_heap.insert(11)
my_heap.insert(10)

print(my_heap.delete_min())  # removing min node i.e 5


"""

Heap is a special tree structure in which each parent node is less than or equal to its child node.
Then it is called a Min Heap. If each parent node is greater than or equal to its child node then it is called a max heap.


MinHeap operations

    Insertion O(logn)O(log n)O(logn): Finding the exact position of the new element is performed in lognlog nlogn since it is only compared with the position of the parent nodes.
    Delete Min O(logn)O(log n)O(logn): After the minimum element is removed, the heap has to put the new root in place.
    Find Min O(1)O(1)O(1): This is possible because the heap data structure always has the minimum element on the root node.
    Heapify O(n)O(n)O(n): This operation rearranges all the nodes after deletion or insertion operation. The cost of this operation is nnn since all the elements have to be moved to keep the heap properties.
    Delete O(logn)O(log n)O(logn): A specific element from the heap can be removed in lognlog nlogn time.

"""

"""
Min Heap Implementation in Python

            5                      13
         /      \               /       \  
       10        15           16         31 
      /                      /  \        /  \
    30                     41    51    100   41
    
"""


class MinHeap:
    def __init__(self):
        """
        On this implementation the heap list is initialized with a value
        """
        self.heap_list = [0]
        self.current_size = 0

    def sift_up(self, i):
        """
        Moves the value up in the tree to maintain the heap property.
        """
        # While the element is not the root or the left element
        while i // 2 > 0:
            # If the element is less than its parent swap the elements
            if self.heap_list[i] < self.heap_list[i // 2]:
                self.heap_list[i], self.heap_list[i // 2] = self.heap_list[i // 2], self.heap_list[i]
            # Move the index to the parent to keep the properties
            i = i // 2

    def insert(self, k):
        """
        Inserts a value into the heap
        """
        # Append the element to the heap
        self.heap_list.append(k)
        # Increase the size of the heap.
        self.current_size += 1
        # Move the element to its position from bottom to the top
        self.sift_up(self.current_size)

    def sift_down(self, i):
        # if the current node has at least one child
        while (i * 2) <= self.current_size:
            # Get the index of the min child of the current node
            mc = self.min_child(i)
            # Swap the values of the current element is greater than its min child
            if self.heap_list[i] > self.heap_list[mc]:
                self.heap_list[i], self.heap_list[mc] = self.heap_list[mc], self.heap_list[i]
            i = mc

    def min_child(self, i):
        # If the current node has only one child, return the index of the unique child
        if (i * 2) + 1 > self.current_size:
            return i * 2
        else:
            # Herein the current node has two children
            # Return the index of the min child according to their values
            if self.heap_list[i * 2] < self.heap_list[(i * 2) + 1]:
                return i * 2
            else:
                return (i * 2) + 1

    def delete_min(self):
        # Equal to 1 since the heap list was initialized with a value
        if len(self.heap_list) == 1:
            return 'Empty heap'

        # Get root of the heap (The min value of the heap)
        root = self.heap_list[1]

        # Move the last value of the heap to the root
        self.heap_list[1] = self.heap_list[self.current_size]

        # Pop the last value since a copy was set on the root
        *self.heap_list, _ = self.heap_list

        # Decrease the size of the heap
        self.current_size -= 1

        # Move down the root (value at index 1) to keep the heap property
        self.sift_down(1)

        # Return the min value of the heap
        return root


"""
Driver program
"""
# Same tree as above example.
my_heap = MinHeap()
my_heap.insert(5)
my_heap.insert(6)
my_heap.insert(7)
my_heap.insert(9)
my_heap.insert(13)
my_heap.insert(11)
my_heap.insert(10)

print(my_heap.delete_min())  # removing min node i.e 5
Heap is a special tree structure in which each parent node is less than or equal to its child node. Then it is called a Min Heap. If each parent node is greater than or equal to its child node then it is called a max heap.   MinHeap operations      Insertion O(logn)O(log n)O(logn): Finding the exact position of the new element is performed in lognlog nlogn since it is only compared with the position of the parent nodes.     Delete Min O(logn)O(log n)O(logn): After the minimum element is removed, the heap has to put the new root in place.     Find Min O(1)O(1)O(1): This is possible because the heap data structure always has the minimum element on the root node.     Heapify O(n)O(n)O(n): This operation rearranges all the nodes after deletion or insertion operation. The cost of this operation is nnn since all the elements have to be moved to keep the heap properties.     Delete O(logn)O(log n)O(logn): A specific element from the heap can be removed in lognlog nlogn time. Min Heap Implementation in Python              5                      13          /      \               /       \          10        15           16         31        /                      /  \        /  \     30                     41    51    100   41 On this implementation the heap list is initialized with a value Moves the value up in the tree to maintain the heap property. # While the element is not the root or the left element # If the element is less than its parent swap the elements # Move the index to the parent to keep the properties Inserts a value into the heap # Append the element to the heap # Increase the size of the heap. # Move the element to its position from bottom to the top # if the current node has at least one child # Get the index of the min child of the current node # Swap the values of the current element is greater than its min child # If the current node has only one child, return the index of the unique child # Herein the current node has two children # Return the index of the min child according to their values # Equal to 1 since the heap list was initialized with a value # Get root of the heap (The min value of the heap) # Move the last value of the heap to the root # Pop the last value since a copy was set on the root # Decrease the size of the heap # Move down the root (value at index 1) to keep the heap property # Return the min value of the heap Driver program # Same tree as above example. # removing min node i.e 5