FilesExpand file tree

master

/

priority_queue.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (46 loc) · 1.75 KB

master

/

priority_queue.py

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (46 loc) · 1.75 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

"""

Implementation of priority queue using linear array.

Insertion - O(n)

Extract min/max Node - O(1)

"""

import itertools

class PriorityQueueNode:

def __init__(self, data, priority):

self.data = data

self.priority = priority

def __repr__(self):

return "{}: {}".format(self.data, self.priority)

class PriorityQueue:

def __init__(self, items=None, priorities=None):

"""Create a priority queue with items (list or iterable).

If items is not passed, create empty priority queue."""

self.priority_queue_list = []

if items is None:

return

if priorities is None:

priorities = itertools.repeat(None)

for item, priority in zip(items, priorities):

self.push(item, priority=priority)

def __repr__(self):

return "PriorityQueue({!r})".format(self.priority_queue_list)

def size(self):

"""Return size of the priority queue.

"""

return len(self.priority_queue_list)

def push(self, item, priority=None):

"""Push the item in the priority queue.

if priority is not given, priority is set to the value of item.

"""

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 item with the lowest priority.

"""

# remove and return the first node from the queue

return self.priority_queue_list.pop().data