What is the difference between heappop and pop(0) on a sorted list?

Question

I have a list stored in this format: [(int, (int, int)), ...]

My code looks like this for the first case.

heap.heappush(list_, (a, b))             # b is a tuple
while len(list_):
    temp = heap.heappop(list_)[1]

Now my ideal implementation would be

list_.append(a, b)                       # b is a tuple
while len(list_):
    list_.sort(key = lambda x: x[0])
    temp = list_.pop(0)[1]

The second implementation causes issues in other parts of my code. Is there any reason the second is incorrect, and how could I correct it to work like the heapq

EDIT: I know heappop() pops the smallest value out, which is why I have sorted the list based off of the 'a' (which heappop uses too, I assume)

Answer 1

To work with heapq you have to be aware python implements min heaps. That means the element at index 0 is always the smallest.

Here is what you want implemented with heapq:

import heapq
from typing import Tuple

class MyObject:
 def __init__(self, a: int, b: Tuple(int, int)):
  self.a = a
  self.b = b
 
 def __lt__(self, other):
  return self.a < other.a

l = [MyObject(..,..), MyObject(..,..),..,MyObject(..,..)] # your list

heapq.heapify(l) # convert l to a heap
heapq.heappop(l) # retrieves and removes the smallest element (which lies at index 0)
# After popping the smallest element, the heap internally rearranges the elements to get the new smallest value to index 0. I.e. it maintaines the "heap variant" automatically and you don't need to explicitly sort!

Notice:

• I didn't need to sort. The heap is by nature a semi-sorted structure
• I needed to create a dedicated class for my objects. This is cleaner than working with tuples of tuples and also allowed me to override less than lt so that the heap knows how to create the tree internally

Here is more detailed info for the avid reader :D

When you work with heaps then you shouldn't need to explicitly sort. A heap by nature is a semi-sorted topology that (in the case of python heapq) keeps the smallest element at index 0. You don't however, see the tree structure underneath (remember, a heap is a tree in whicheach parent node is smaller than all its children and descendants).

Moreover, you don't need to append the elements one by one. Rather use heapq.heapify(). This will also ensure that no redundant heapify-up/heapify-down operations. Otherwise, you will have a serious run time issue if your list is huge :)