pydoc > _heapq

man perldoc info pydoc3 ri search

📖 NAME

_heapq - Heap queue algorithm (a.k.a. priority queue).

🚀 Quick Reference

Use Case	Command	Description
Create empty heap	heap = []	Initialize an empty list as heap.
Push item	heappush(heap, item)	Push item onto heap, maintaining heap invariant.
Pop smallest	heappop(heap)	Pop and return the smallest item.
Peek smallest	heap[0]	Access smallest item without popping.
Transform list to heap	heapify(x)	Convert list into heap in-place, O(len(x)).
Replace smallest	heapreplace(heap, item)	Pop smallest and push new item, more efficient than separate pop/push.

📝 DESCRIPTION

Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that a[0] is always its smallest element.

Usage:

heap = []            # creates an empty heap
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
item = heap[0]       # smallest item on the heap without popping it
heapify(x)           # transforms list into a heap, in-place, in linear time
item = heapreplace(heap, item) # pops and returns smallest item, and adds
                               # new item; the heap size is unchanged

Our API differs from textbook heap algorithms as follows:

• 🔹 We use 0‑based indexing. This makes the relationship between the index for a node and the indexes for its children slightly less obvious, but is more suitable since Python uses 0‑based indexing.
• 🔹 Our heappop() method returns the smallest item, not the largest.

These two make it possible to view the heap as a regular Python list without surprises: heap[0] is the smallest item, and heap.sort() maintains the heap invariant!

🔧 FUNCTIONS

• heapify(heap, /) — Transform list into a heap, in-place, in O(len(heap)) time.
• heappop(heap, /) — Pop the smallest item off the heap, maintaining the heap invariant.
• heappush(heap, item, /) — Push item onto heap, maintaining the heap invariant.
• heappushpop(heap, item, /) — Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().
• heapreplace(heap, item, /) — Pop and return the current smallest value, and add the new item. This is more efficient than heappop() followed by heappush(), and can be more appropriate when using a fixed-size heap. Note that the value returned may be larger than item! That constrains reasonable uses of this routine unless written as part of a conditional replacement:

  if item > heap[0]:
      item = heapreplace(heap, item)

📊 DATA

__about__ = 'Heap queues\n\n[explanation by François Pinard]\n\nH... t...'

📁 FILE

(built-in)

📖 NAME 🚀 Quick Reference 📝 DESCRIPTION 🔧 FUNCTIONS 📊 DATA 📁 FILE