Rookie - 6 months ago 29

Python Question

I have made a priority queue whose functions use my binary heaps functions. However, in my testing file I am trying to print out my Queue to look something like this.

`Your queue looks like this: 15 -> 45 -> 10 -> 100`

Somewhere like that, however it keeps printing out where the queue is stored rather than the items in the queue, an example of this:

`<PriorityQueue.PriorityQueue object at 0x01E95530>`

I read up on the pythonDocs and concluded I need a

`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

Above is my Heap class where my PriorityQueue takes from:

Below is my PQ class and my test file.

`#PriorityQueue.py`

from MyHeap import Heap

class PriorityQueue(object):

def __init__(self):

self.heap = Heap()

def enqueue(self, priority, item):

'''Post: Item is inserted with specified priority in the PQ.'''

self.heap.insert((priority, item))

return item

def first(self):

'''Post: Returns but does not remove the highest priority item from the PQ.'''

return self.heap.size()

def dequeue(self):

'''Post: Removes and returns the highest priority item from the PQ.'''

if self.heap.size() is None:

raise ValueError("Error your queue is empty.")

x = self.first()

self.heap.delete_max()

return x

def size(self):

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

return self.heap.size()

`from PriorityQueue import PriorityQueue`

PQ = PriorityQueue()

print(PQ.enqueue(1, 10))

print(PQ.enqueue(2, 5))

print(PQ.enqueue(3, 90))

print PQ

print(PQ.size())

EDIT: I tried to do the following:

`def __str__(self):`

return str(self.heap)

This only prints out this:

`<MyHeap.Heap object at 0x01E255F0>`

Answer

Ok, the idea of `__str__`

is to return some sort of string that represents the object in a human-readable way. You have to construct the string and then whatever you return will be printed instead of

```
<PriorityQueue.PriorityQueue object at 0x01E95530>
```

In your case, we have to return the items of `self.heap.heap`

, separated by `->`

. This would work to get the output like you described:

```
def __str__(self):
if self.size():
heap_items = [str(i) for i in self.heap.heap if i]
heap_items_str = ' -> '.join(heap_items)
return "Your queue looks like this: {}".format(heap_items_str)
else:
return "Your queue is empty."
```