Added and updated solutions with priority queue

Meto Trajkovski · Meto Trajkovski · commit ad9bf5e77593 · 2019-12-13T17:43:03.000+01:00
diff --git a/Linked Lists/merge_k_sorted_ll.py b/Linked Lists/merge_k_sorted_ll.py
@@ -35,34 +35,33 @@ def __lt__(self, other):
         return self.val < other.val
 
 # priority queue
-class MyHeap:
+class PriorityQueue:
     def __init__(self):
         self.data = []
 
     def push(self, node):
-        heapq.heappush(self.data, node)
+        heapq.heappush(self.data, PQNode(node))
 
     def pop(self):
-        return heapq.heappop(self.data)
+        return heapq.heappop(self.data).node
 
     def is_empty(self):
         return len(self.data) == 0
 
 def merge_k_lists_1(lists):
-    heap = MyHeap()
+    heap = PriorityQueue()
 
     # add all linked lists in the heap
     for node in lists:
         if node is not None:
-            heap.push(PQNode(node))
+            heap.push(node)
 
     result = ListNode(-1)
     pointer = result
 
     while not heap.is_empty():
         # in each step remove the min list from the heap
-        el = heap.pop()
-        node = el.node
+        node = heap.pop()
 
         # add the min list to the result
         pointer.next = node
@@ -71,7 +70,7 @@ def merge_k_lists_1(lists):
         node = node.next
         if node is not None:
             # take the next node from the min list and add it in the heap
-            heap.push(PQNode(node))
+            heap.push(node)
 
     return result.next
 
diff --git a/Lists/k_closest_points.py b/Lists/k_closest_points.py
@@ -42,7 +42,7 @@ def kth_closest(arr, k, left, right, pt):
         kth_closest(arr, k, pivot + 1, right, pt)
 
 def pivoting(arr, left, right, pt):
-    # O(N) pivoting
+    # Linear time complexity pivoting
     # takes the last element as pivot
     pivot_dist = sqr_dist(pt, arr[right])
     new_pivot = left
diff --git a/Lists/kth_smallest.py b/Lists/kth_smallest.py
@@ -46,7 +46,7 @@ def kth_smallest(arr, k, left, right):
     return arr[pivot]
 
 def pivoting(arr, left, right):
-    # O(N) pivoting
+    # Linear time complexity pivoting
     # takes the last element as pivot
     pivot = right
     new_pivot = left
diff --git a/Lists/running_median.py b/Lists/running_median.py
@@ -16,7 +16,7 @@
 2
 
 =========================================
-Using 2 heaps (priority queues) balance the left and right side of the stream.
+Using 2 heaps (max and min Priority Queues) balance the left and right side of the stream.
     Time Complexity:    O(N LogN)
     Space Complexity:   O(N)
 '''
@@ -26,36 +26,36 @@
 # Solution #
 ############
 
-from heapq import heappush, heappop
+import heapq
 
 class PriorityQueue:
-    def __init__(self, isMin=True):
+    def __init__(self, is_min=True):
         self.data = []
-        self.isMin = isMin
+        self.is_min = is_min
 
     def push(self, el):
-        if not self.isMin:
+        if not self.is_min:
             el = -el
-        heappush(self.data, el)
+        heapq.heappush(self.data, el)
 
     def pop(self):
-        el = heappop(self.data)
-        if not self.isMin:
+        el = heapq.heappop(self.data)
+        if not self.is_min:
             el = -el
         return el
 
     def peek(self):
         el = self.data[0]
-        if not self.isMin:
+        if not self.is_min:
             el = -el
         return el
 
     def count(self):
         return len(self.data)
 
 def running_median(stream):
-    left_heap = PriorityQueue(False)
-    right_heap = PriorityQueue()
+    left_heap = PriorityQueue(False) # Max Priority Queue
+    right_heap = PriorityQueue() # Min Priority Queue
 
     # left_heap will have always same number of elements or 1 element more than right_heap
     for number in stream:
diff --git a/Lists/top_k_frequent_elements.py b/Lists/top_k_frequent_elements.py
@@ -2,6 +2,7 @@
 Top K Frequent Elements
 
 Given a non-empty array of integers, return the k most frequent elements.
+The order of the result isn't important.
 
 Input: [1, 1, 1, 2, 2, 3], 2
 Output: [1, 2]
@@ -10,12 +11,13 @@
 Output: [1]
 
 =========================================
-Using Priority Queue, add each frequency and remove the last if there are more than K elements inside the Priority Queue.
-    Time Complexity:    O(N LogK)
+Using Min Priority Queue, in each step add an element with its frequency and remove the element with the smallest frequency 
+if there are more than K elements inside the Priority Queue. This solution isn't much faster than sorting the frequencies. 
+    Time Complexity:    O(U LogK)   , U in this case is the number of unique elements (but all elements from the array could be unique, so because of that U can be equal to N)
     Space Complexity:   O(N)
 Using pivoting, this solution is based on the quick sort algorithm (divide and conquer). 
-Same pivoting solution as the nth_smallest.py,
-    Time Complexity:    O(N)
+Same pivoting solution as the nth_smallest.py.
+    Time Complexity:    O(U)
     Space Complexity:   O(N)
 '''
 
@@ -24,10 +26,37 @@
 # Solution 1 #
 ##############
 
+import heapq
+
+# priority queue comparator class
+# acctualy in this case you don't need a comparator class, because the elements are tuples
+# and comparison operator can work with tuples 
+# (The comparison starts with a first element of each tuple. If they do not compare to =,< or > then it proceed to the second element and so on.)
+class PQElement:
+    def __init__(self, el):
+        self.frequency, self.val = el
+
+    def __lt__(self, other):
+        return self.frequency < other.frequency
+
+# priority queue
+class PriorityQueue:
+    def __init__(self):
+        self.data = []
+
+    def push(self, el):
+        heapq.heappush(self.data, PQElement(el))
+
+    def pop(self):
+        return heapq.heappop(self.data)
+
+    def count(self):
+        return len(self.data)
+
 def top_k_frequent_1(nums, k):
     frequency = {}
 
-    # count the frequency of each element
+    # count the frequency of each unique element
     for num in nums:
         if num in frequency:
             frequency[num] += 1
@@ -42,7 +71,17 @@ def top_k_frequent_1(nums, k):
     if k < 1:
         return []
 
-    # TODO: Implement Priority Queue and solve it
+    heap = PriorityQueue()
+    for el in arr:
+        # push all elements
+        heap.push(el)
+        # pop the element with smallest frequency
+        if heap.count() > k:
+            heap.pop()
+
+    # take all elements from the heap
+    # no need from K times heap.pop() (K LogK), because we already have the array with data (K)
+    return [el.val for el in heap.data]
 
 
 ##############
@@ -52,7 +91,7 @@ def top_k_frequent_1(nums, k):
 def top_k_frequent_2(nums, k):
     frequency = {}
 
-    # count the frequency of each element
+    # count the frequency of each unique element
     for num in nums:
         if num in frequency:
             frequency[num] += 1
@@ -67,7 +106,7 @@ def top_k_frequent_2(nums, k):
     if k < 1:
         return []
 
-    # pivoting, find the first k element with the biggest frequency, O(U), U = num of unique nums
+    # pivoting, find the first k elements with the biggest frequency, O(U), U = num of unique nums
     k -= 1
     left = 0
     right = n - 1
@@ -86,7 +125,7 @@ def top_k_frequent_2(nums, k):
     return None
 
 def pivoting(arr, left, right):
-    # O(N) pivoting
+    # Linear time complexity pivoting
     # takes the last element as pivot
     pivot = right
     new_pivot = left
@@ -95,7 +134,7 @@ def pivoting(arr, left, right):
     # and put all elements bigger than the pivot (last element) in the first K spots
     # with the new_pivot we're "counting" how many bigger elements are there
     for j in range(left, right):
-        if arr[j] > arr[pivot]:
+        if arr[j][0] > arr[pivot][0]:
             swap(arr, new_pivot, j)
             new_pivot += 1
 
