title: Priority Queue using a Max-Heap Data Structure
body: <p>I am implementing a priority queue using a max-heap data structure in Python. I'm using several names that have numbers associated with them as their priority (9 being the highest and 1 being the lowest). The issue I am facing is that when I dequeue an item from the priority queue, it does not dequeue the item with highest priority. I assume this means there is a problem with my enqueue and it is not inserting the items into the correct position in the heap based on their priority. If anyone could help me fix this, it would be greatly appreciated.</p>
  
  <p>My priority queue code:</p>
  
  <pre><code>from Heap import Heap
  
  class priorityQ(object):
      def __init__(self):
          self.PQ = Heap()
  
      def enqueue(self, priority, item):
          self.PQ.insert((priority, item))
  
      def dequeue(self):
          if self.PQ.size() == 0:
              raise ValueError("Empty Queue")
          return self.PQ.delete_max()
  
      def first(self):
          return self.PQ.get_max()
  
      def size(self):
          return self.PQ.size()
  
  def main():
      myHeap = priorityQ()
      print(myHeap.size())
      myHeap.enqueue(8, "Kaneda")
      myHeap.enqueue(6, "Masaru")
      myHeap.enqueue(9, "Akira")
      myHeap.enqueue(4, " Kei")
      myHeap.enqueue(5, "Takashi")
      myHeap.enqueue(2, "Shikishima")
      myHeap.enqueue(3, "Kiyoko")
      myHeap.enqueue(1, "Yamagata")
      myHeap.enqueue(7, "Tetsuo")
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
      myHeap.dequeue()
      print(myHeap.first())
      print(myHeap.size())
  </code></pre>
  
  <p>Output after I run the code and call main:</p>
  
  <pre><code>0
  (9, 'Akira')
  9
  (7, 'Tetsuo')
  8
  (5, 'Takashi')
  7
  (4, 'Kei')
  6
  (3, 'Kiyoko')
  5
  (2, 'Shikishima')
  4
  (1, 'Yamagata')
  3
  (1, 'Yamagata')
  2
  (1, 'Yamagata')
  1
  None
  0
  </code></pre>
  
  <p>Max-heap code (provided by textbook):</p>
  
  <pre><code># Heap.py
  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 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 &lt;= self.heap_size:
              child = position * 2
              # if right child, determine maximum of two children
              if (child != self.heap_size and 
                  self.heap[child+1] &gt; self.heap[child]):
                  child += 1
              if self.heap[child] &gt; 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 &gt; 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 &gt; 0:
                  self._heapify(1)
              return max_item
  
      def get_max(self):
          if self.heap_size &gt; 0:
              max_item = self.heap[1]
              self.heap[1] = self.heap[self.heap_size]
              if self.heap_size &gt; 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 &gt; 0 and self.heap[parent] &lt; item:
              # move item down
              self.heap[position] = self.heap[parent]
              position = parent
              parent = position // 2
          # put new item in 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
  </code></pre>