<p>Given an array of integers&nbsp;<code>arr</code>&nbsp;and an integer <code>k</code>.&nbsp;Find the <em>least number of unique integers</em>&nbsp;after removing <strong>exactly</strong> <code>k</code> elements<b>.</b></p>

<ol>
</ol>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input: </strong>arr = [5,5,4], k = 1
<strong>Output: </strong>1
<strong>Explanation</strong>: Remove the single 4, only 5 is left.
</pre>
<strong class="example">Example 2:</strong>

<pre>
<strong>Input: </strong>arr = [4,3,1,1,3,3,2], k = 3
<strong>Output: </strong>2
<strong>Explanation</strong>: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length&nbsp;&lt;= 10^5</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 10^9</code></li>
	<li><code>0 &lt;= k&nbsp;&lt;= arr.length</code></li>
</ul>
class MinHeap:
    def __init__(self):
        self.heap = []

    def length(self):
        return len(self.heap)

    def print_heap(self):
        return str(self.heap)

    def peek(self):
        return self.heap[0]        
    
    def insert(self, value):
        self.heap.append(value)
        self.bubble_up(len(self.heap) - 1)
    
    def bubble_up(self, index):
        parent = (index - 1) // 2
        
        if index > 0 and self.heap[index][0] < self.heap[parent][0]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self.bubble_up(parent)
    
    def pop(self):
        if len(self.heap) == 0:
            raise IndexError("Heap is empty")
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.bubble_down(0)

        return root

    def bubble_down(self, index):        
        min_index = index
        left_child = 2 * index + 1
        right_child = 2 * index + 2

        if left_child < len(self.heap) and self.heap[left_child][0] < self.heap[min_index][0]:
            min_index = left_child
        if right_child < len(self.heap) and self.heap[right_child][0] < self.heap[min_index][0]:
            min_index = right_child

        if min_index != index:
            self.heap[index], self.heap[min_index] = self.heap[min_index], self.heap[index]
            self.bubble_down(min_index)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int: 
        count = Counter(arr)
        heap = MinHeap()

        for num in count:
            heap.insert((count[num], num))
        
        for i in range(k):
            freq, num = heap.pop()
            if freq > 1:
                heap.insert((freq - 1, num))

        return heap.length()


34100