Making a priority queue using a Heap. Without using "queue" or "heapq"

Question

I have made a heap class and I am trying to make a PriorityQueue class as well so both of them can work together. However, I need help on the Priority Queue part of my code. I have already made a working Heap. I tried looking up help on the internet but I keep getting answers with people using either the "queue" or "heapq" python implementation. Could anyone help me on how to make a working Priority Queue class? I have the basic function names written down but I have no idea on where to go from there. Please I have been stuck on this for awhile and really need some help. Here is my working Heap Code.

class Heap(object):

    def __init__(self, items=None):

        '''Post: A heap is created with specified items.'''

        self.heap = [None]
        if items is None:
            self.heap_size = 0
        else:
            self.heap += items
            self.heap_size = len(items)
            self._build_heap()

    def size(self):

        '''Post: Returns the number of items in the heap.'''

        return self.heap_size

    def _heapify(self, position):

        '''Pre: Items from 0 to position - 1 satisfy the Heap property.
       Post: Heap Property is satisfied for the entire heap.'''

        item = self.heap[position]
        while position * 2 <= self.heap_size:
            child = position * 2
            # If the right child, determine the maximum of two children.
            if (child != self.heap_size and self.heap[child+1] > self.heap[child]):
                child += 1
            if self.heap[child] > item:
                self.heap[position] = self.heap[child]
                position = child
            else:
                break
        self.heap[position] = item

    def delete_max(self):

        '''Pre: Heap property is satisfied
       Post: Maximum element in heap is removed and returned. '''

        if self.heap_size > 0:
            max_item = self.heap[1]
            self.heap[1] = self.heap[self.heap_size]
            self.heap_size -= 1
            self.heap.pop()
            if self.heap_size > 0:
                self._heapify(1)
            return max_item

    def insert(self, item):

        '''Pre: Heap Property is Satisfied.
       Post: Item is inserted in proper location in heap.'''

        self.heap_size += 1
        # extend the length of the list.
        self.heap.append(None)
        position = self.heap_size
        parent = position // 2
        while parent > 0 and self.heap[parent] < item:
            # Move the item down.
            self.heap[position] = self.heap[parent]
            position = parent
            parent = position // 2
        # Puts the new item in the correct spot.
        self.heap[position] = item

    def _build_heap(self):

        ''' Pre: Self.heap has values in 1 to self.heap_size
           Post: Heap property is satisfied for entire heap. '''

        # 1 through self.heap_size.

        for i in range(self.heap_size // 2, 0, -1): # Stops at 1.
            self._heapify(i)

    def heapsort(self):

        '''Pre: Heap Property is satisfied.
           Post: Items are sorted in self.heap[1:self.sorted_size].'''

        sorted_size = self.heap_size

        for i in range(0, sorted_size -1):
            # Since delete_max calls pop to remove an item, we need to append a dummy value to avoid an illegal index.
            self.heap.append(None)
            item = self.delete_max()
            self.heap[sorted_size - i] = item

So this is working but like I previously stated I am having trouble on how to make a priority queue out of this? I know asking for code is wrong, but I'm desperate could anyone help me out here? I have the basic rundown on what I want my priority code to do..

#PriorityQueue.py
from MyHeap import Heap


class PriorityQueue(object):

    def enqueue(self, item, priority):
        '''Post: Item is inserted with specified priority in the PQ.'''

    def first(self):
    '''Post: Returns but does not remove the highest priority item from the PQ.'''

    def dequeue(self):
    '''Post: Removes and returns the highest priority item from the PQ.'''

    def size(self):
    '''Post: Returns the number of items in the PQ.'''
        return Heap.heap_size

Is there a specific place you're getting stuck? For the most part, the functions you have stubbed out in the priority queue class just need to call functions from the heap class. Are you having trouble figuring out what that mapping is? — seaotternerd
@seaotternerd Yeah that is what I am having trouble with is the mapping to go along side of setting the priority. — Cooper
There are a few ways you could potentially handle priority. The simplest and most versatile is probably to make a key-value pair class, where each object holds two things: a priority and the thing being stored. It should also have a comparison operator that compares based on the priority. In insert, you can create a key value pair based on the input to insert and then put it into the heap. — seaotternerd

Blckknght Blckknght · Accepted Answer · 2015-04-27T02:15:43

I think the key idea you're missing to implement your PriorityQueue class is that each PriorityQueue instance should have a Heap instance as an attribute. Set it up in __init__:

class PriorityQueue(object):
    def __init__(self)
        self.heap = Heap()

When a user makes a call to a PriorityQueue method, that method will mostly just make a call to a method of self.heap, with just a little extra work modifying the arguments or the return value. The items to insert into the heap should probably be (priority, value) tuples, since they will compare appropriately (higher priority items comparing higher).

Note that if you compare code written for heapq with your Heap, you'll need to modify the logic for the indexes and priorities, since heapq implements a zero-indexed min-heap, and your code implements a one-indexed max-heap.

Making a priority queue using a Heap. Without using "queue" or "heapq"

1 Answers