Cuttings Cuttings | Things of interest.
Things of interest.


 
December 14, 2018

Heaps of Heapq


Principally data structures, not lists.

Currently reading about the heapq algorithm. Good comments from Stack Overflow on its use - principally for priority queues, and root extraction:

  1. This means that it is very efficient to find the smallest element (just take heap[0]), which is great for a priority queue. After that, the next 2 values will be larger (or equal) than the 1st, and the next 4 after that are going to be larger than their ‘parent’ node, then the next 8 are larger, etc.

    A heap can be turned back into a sorted list very efficiently:

    def heapsort(heap):
        return [heapq.heappop(heap) for _ in range(len(heap))]
    

    You’d use a heap if you are only interested in the smallest value, or the first n smallest values, especially if you are interested in those values on an ongoing basis; adding new items and removing the smallest is very efficient indeed, more so than resorting the list each time you added a value.

  2. Moral: If you write an algorithm using a sorted list but only ever inspect and remove from one end, then you can make the algorithm more efficient by using a heap.

  3. In general, heap data structure is different from a sorted list in that it sacrifices some information about whether any particular element is bigger or smaller than any other. Heap only can tell, that this particular element is less, than it’s parent and bigger, than it’s children. The less information a data structure stores, the less time/memory it takes to modify it. Compare the complexity of some operations between a heap and a sorted array:


 
 
© 1997 - 2018 / Info