Repository: keon/algorithms
Pull request #273 (2018-05-03 11:54:40)

Update priority_queue.py
- refactor `insert` and `delete` -> `push` and `pop`. Because `pop` seems more natural while returning the deleted item (rather than `delete`)
- `push` now takes data and priority(optional), and constructs a `PriorityQueueNode` inside the method for inserting. This simplifies the usage.
- used `collections.deque()` for O(1) popleft operation.
- add `__repr__` method.
(refer #271 )

coveralls: ## Pull Request Test Coverage Report for [Build 242](https://coveralls.io/builds/16814927)

* **0** of **0**  **(NaN%)** changed or added relevant lines in **0** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage remained the same at **91.151%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/16814927/badge)](https://coveralls.io/builds/16814927) |
| :-- | --: |
| Change from base [Build 240](https://coveralls.io/builds/16813427): |  0.0% |
| Covered Lines: | 2709 |
| Relevant Lines: | 2972 |

---
##### 💛  - [Coveralls](https://coveralls.io)

SaadBenn: Excellent job @goswami-rahul I'll take a look at it.
SaadBenn: Your `push` method is so much better than mine and overall the code is more compact. I like it. Great job at refactoring. @goswami-rahul  I think it's good to merge now but I'll wait for @danghai.

Patch:
diff --git a/queues/priority_queue.py b/queues/priority_queue.py
index 92d8c4a..a28ae96 100644
--- a/queues/priority_queue.py
+++ b/queues/priority_queue.py
@@ -1,8 +1,12 @@
 """
-Implementation of priority queue
+Implementation of priority queue using linear array.
+Insertion - O(n)
+Extract min/max Node - O(1)
 """
+import collections
 
-class PriorityQueueNode:	
+
+class PriorityQueueNode:
 	def __init__(self, data, priority):
 		self.data = data
 		self.priority = priority
@@ -12,30 +16,24 @@ class PriorityQueueNode:
 
 class PriorityQueue:
 	def __init__(self):
-		self.priority_queue_list = []
+		self.priority_queue_list = collections.deque()
+
+	def __repr__(self):
+	    return "PriorityQueue({!r})".format(list(self.priority_queue_list))
 
 	def size(self):
 		return len(self.priority_queue_list)
 
-	def insert(self, node):
-		# if queue is empty
-		if self.size() == 0:
-			self.priority_queue_list.append(node)
-		else:
-			 # traverse the queue to find the right place for new node
-			 for index, current in enumerate(self.priority_queue_list):
-			 	if current.priority < node.priority:
-			 		# if we have traversed the complete queue
-			 		if index == self.size() - 1:
-			 			# add new node at the end
-			 			self.priority_queue_list.insert(index + 1, node)
-			 		else:
-			 			continue
-			 	else:
-			 		self.priority_queue_list.insert(index, node)
-			 		return True
-
-	def delete(self):
-		# remove the first node from the queue
-		return self.priority_queue_list.pop(0)
-										
\ No newline at end of file
+	def push(self, item, priority=None):
+		priority = item if priority is None else priority
+		node = PriorityQueueNode(item, priority)
+		for index, current in enumerate(self.priority_queue_list):
+			if current.priority > node.priority:
+				self.priority_queue_list.insert(index, node)
+				return
+		# when traversed complete queue
+		self.priority_queue_list.append(node)
+
+	def pop(self):
+		# remove and return the first node from the queue
+		return self.priority_queue_list.popleft()


Test patch:
diff --git a/tests/test_queues.py b/tests/test_queues.py
index 23afc29..a37d95f 100644
--- a/tests/test_queues.py
+++ b/tests/test_queues.py
@@ -1,7 +1,7 @@
 from queues.queue import ArrayQueue, LinkedListQueue
 from queues.max_sliding_window import max_sliding_window
 from queues.reconstruct_queue import reconstruct_queue
-
+from queues.priority_queue import PriorityQueue, PriorityQueueNode
 import unittest
 
 class TestQueue(unittest.TestCase):
@@ -85,6 +85,19 @@ class TestSuite(unittest.TestCase):
         self.assertEqual([[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]],
                          reconstruct_queue([[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]))
 
+class TestPriorityQueue(unittest.TestCase):
+    """
+        Test suite for the PriorityQueue data structures.
+    """
+    def test_PriorityQueue(self):
+        queue = PriorityQueue()
+        queue.push(3)
+        queue.push(4)
+        queue.push(1)
+        queue.push(6)
+        self.assertEqual(4,queue.size())
+        self.assertEqual(str(1) + ": " + str(1),str(queue.pop()))
+
 if __name__ == "__main__":
 
     unittest.main()