How can I implement Priority Queue without using any built-in functions?

Question

this is my first question here ever, so formatting and such might be a little off. Please don't hate me :)

So what I am doing is making a class called PQUEUE and what I have already is:

class qNode:
    def __init__(self,data=None, next=None):
        self.data = data
        self.next = next
    def __str__(self):
        return str(self.data)

class PQUEUE:

    def __init__(self):
        self.head = None
        self.foot = None

    def push(self, value=None, priority=0):
        #This is what I want to make

    def pop(self):
        x = self.front.data
        self.front = self.front.next
        return x

    def clear(self):
        self._head = None
        self._foot = None

I am trying to make make a Priority Queue class (as you can see) without using heapq/queue classes or the built-in list methods.

What I can't figure out is how I would go on about doing this. I've tried searching everywhere online but everywhere I look people are doing this by either importing or using the built-in list methods.

Help very appreciated ! :)

You basically have to implement heapq yourself for this. Judging by the code you've written, you don't seem to have any familiarity with heaps. Look up "binary heap" and implement one of those. — user2357112
– user2357112, Commented Apr 8, 2016 at 19:30
It's basically a list sorted by priority, consider using bisect.bisect_left() to compute the insert index, and then use list.insert(). — Nick
– Nick, Commented Apr 8, 2016 at 19:34
@Nick: That's still punting all the work to the standard library, though. Using bisect seems to be about as contrary to the spirit of the task as using heapq. Also, a sorted list has linear-time insertion instead of the logarithmic-time insertion of a binary heap. — user2357112
– user2357112, Commented Apr 8, 2016 at 19:40
I don't hate you, but I downvoted your question and voted to close as "Too Broad" because you're basically asking us to do your homework for you. This type of question is inappropriate for SO. What you should do is research algorithms for implementing a priority queue and try to implement them. If and when you run into a concept you don't understand, then narrow down exactly what it is you don't understand, research it, and if you still can't find an answer, you can come back and formulate a question around it. — jpmc26
– jpmc26, Commented Apr 8, 2016 at 20:01

Wayne Werner · Accepted Answer · 2016-04-08 19:55:17Z

2

It depends on what your definition of priority is, but you're going to have to iterate over your collection yourself, looking for the place to insert the next node:

node = self.head
while node.next and node.next.priority > priority:
    node = node.next

if node.next is None:
    node.next = qNode(value=value, next=None, priority=priority)
    self.foot = node.next
else:
    new_node = qNode(value=value, next=node.next, priority=priority)
    node.next = new_node

You'll have to add a priority to your qNode, of course, and you may have to adjust exactly where you're going to insert, but this should get you most of the way there.

answered Apr 8, 2016 at 19:55

Wayne Werner

52.3k35 gold badges213 silver badges304 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ashisahu · Accepted Answer · 2018-09-08 08:07:50Z

Here is the implementation of priority queue in python using linked list:-

# Python code to implement Priority Queue using Linked List
# Node class 
class Node:
    def __init__(self, item, priority):
        self.item = item
        self.next = None
        self.priority = priority

class PriorityQueue:
    def __init__(self):
        self.front = self.rear = None

    # Returns a boolean value indicating whether the queue is empty
    def isEmpty(self):
        return self.front == None

    # Adds the given item to the queue by inserting it in the proper 
    # position based on the given priority. The new node is appended to 
    # the end of the linked list
    def enqueue(self, item, priority):
        newNode = Node(item, priority)
        if not self.rear:
            self.front = self.rear = newNode
            return
        if self.front.priority < newNode.priority:
            newNode.next = self.front
            self.front = newNode
            return
        previous = None
        current = self.front
        while(current and newNode.priority < current.priority):
            previous = current
            current = current.next

        if current:
            previous.next = newNode
            newNode.next = current
        else:
            self.rear.next = newNode
            self.rear = newNode

    # Removes and returns the next item from the queue, which is the 
    # item with the highest priority. If two or more items have the 
    # same priority, those items are removed in FIFO order. An item 
    # cannot be dequeued from an empty queue. 
    def dequeue(self):
        if self.isEmpty():
            print('Queue is empty')
            return
        temp = self.front
        self.front = self.front.next
        if self.front == None:
            self.rear = None
        return temp.item

Collectives™ on Stack Overflow

How can I implement Priority Queue without using any built-in functions?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related