Heap

A binary tree that satisfies the heap property: if B is a child node of node A, then key(A) ≥ key(B). Heap is the most efficient implementation of an abstract data type called a priority queue that supports two mandatory operations — add an element and extract minimum (or maximum, depending on implementation).

Python implements a min-heap (where the smallest value is always at the root) based on a list using the built-in heapq module. If you need a max-heap, with the maximum value at the root, you can use tips from Stackoverflow.

import heapq

h = [211, 1, 43, 79, 12, 5, -10, 0]
heapq.heapify(h)  # Transform a list into a heap
print(h)

heapq.heappush(h, 2)  # Add an element
print(h)

m = heapq.heappop(h)  # Extract the minimum element
print(h, m)

[-10, 0, 5, 1, 12, 211, 43, 79]
[-10, 0, 5, 1, 12, 211, 43, 79, 2]
[0, 1, 5, 2, 12, 211, 43, 79] -10