title: What is Python's heapq module?
body: <p>I tried <a href="https://docs.python.org/3/library/heapq.html" rel="noreferrer">"heapq"</a> and arrived at the conclusion that my expectations differ from what I see on the screen. I need somebody to explain how it works and where it can be useful.</p>
  
  <p>From the book <a href="http://pymotw.com/2/articles/data_structures.html#sorting" rel="noreferrer">Python Module of the Week</a> under paragraph <strong>2.2 Sorting</strong> it is written</p>
  
  <blockquote>
    <p>If you need to maintain a sorted list as you add and remove values,
    check out heapq. By using the functions in heapq to add or remove
    items from a list, you can maintain the sort order of the list with
    low overhead.</p>
  </blockquote>
  
  <p>Here is what I do and get.</p>
  
  <pre><code>import heapq
  heap = []
  
  for i in range(10):
      heap.append(i)
  
  heap
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  
  heapq.heapify(heap)    
  heapq.heappush(heap, 10)    
  heap
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  
  heapq.heappop(heap)
  0    
  heap
  [1, 3, 2, 7, 4, 5, 6, 10, 8, 9] &lt;&lt;&lt; Why the list does not remain sorted?
  
  heapq.heappushpop(heap, 11)
  1
  heap
  [2, 3, 5, 7, 4, 11, 6, 10, 8, 9] &lt;&lt;&lt; Why is 11 put between 4 and 6?
  </code></pre>
  
  <p>So, as you see the "heap" list is not sorted at all, in fact the more you add and remove the items the more cluttered it becomes. Pushed values take unexplainable positions.
  What is going on? </p>