Editing Binary heap (section)

=== Insert then extract ===
Inserting an element then extracting from the heap can be done more efficiently than simply calling the insert and extract functions defined above, which would involve both an <code>upheap</code> and <code>downheap</code> operation. Instead, we can do just a <code>downheap</code> operation, as follows:

# Compare whether the item we're pushing or the peeked top of the heap is greater (assuming a max heap)
# If the root of the heap is greater:
## Replace the root with the new item
## Down-heapify starting from the root
# Else, return the item we're pushing

[[Python (programming language)|Python]] provides such a function for insertion then extraction called "heappushpop", which is paraphrased below.<ref>{{Cite web| title=python/cpython/heapq.py| url=https://github.com/python/cpython/blob/master/Lib/heapq.py|access-date=2020-08-07| website=GitHub| language=en}}</ref><ref>{{Cite web|title=heapq — Heap queue algorithm — Python 3.8.5 documentation| url=https://docs.python.org/3/library/heapq.html#heapq.heappushpop|access-date=2020-08-07| website=docs.python.org|quote=heapq.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().}}</ref> The heap array is assumed to have its first element at index 1.
 // Push a new item to a (max) heap and then extract the root of the resulting heap. 
 // ''heap'': an array representing the heap, indexed at 1
 // ''item'': an element to insert
 // Returns the greater of the two between ''item'' and the root of ''heap''.
 '''Push-Pop'''(''heap'': List<T>, ''item'': T) -> T:
     '''if''' ''heap'' is not empty '''and''' heap[1] > ''item'' '''then''':  // < if min heap
         '''swap''' ''heap''[1] and ''item''
         _downheap(''heap'' starting from index 1)
     '''return''' ''item''
A similar function can be defined for popping and then inserting, which in Python is called "heapreplace":
 // Extract the root of the heap, and push a new item 
 // ''heap'': an array representing the heap, indexed at 1
 // ''item'': an element to insert
 // Returns the current root of ''heap''
 '''Replace'''(''heap'': List<T>, ''item'': T) -> T:
     '''swap''' ''heap''[1] and ''item''
     _downheap(''heap'' starting from index 1)
     '''return''' ''item''