Heaps are specialized tree-based data structures that satisfy the heap property. They’re commonly implemented as priority queues.
- Heapsort: O(n log n) worst-case time complexity.
Basic Heap Operations
Insert / Push
def insert(A, n, value):
n = n + 1
i = n
while i > 0 and A[i//2] > value:
A[i] = A[i//2] # Push down parents until value > parent
i = i//2
A[i] = value # Insert value
Pop
def pop(A, n):
res = A[0]
n = n - 1
A[n-1] = A[0]
heapify(A, 1, n)
return res
Peek
def peek(A):
return A[0]
Heapify
def heapify(A, i, n):
smallest = i
if 2*i < n and A[2*i] < A[smallest]:
smallest = 2*i
if 2*i+1 < n and A[2*i+1] < A[smallest]:
smallest = 2*i+1
if smallest != i:
swap(A[i], A[smallest])
heapify(A, smallest, n)
Note: heapq.heapify(arr) is essentially a build-heap operation: for i⟵n-1 to 0 do heapify(A,i,n). It takes O(n) time, even though each individual heapify operation is O(log n) – turns out the naive bound of O(nlogn) is not a tight bound!
Time Complexities of Heap Operations
| Operation | Time Complexity |
|---|---|
insert |
O(log n) |
pop |
O(log n) |
peek |
O(1) |
heapify |
O(n) |
Python’s heapq Library
import heapq
arr = [2, 1, 5, 4]
heapq.heapify(arr) # [1, 2, 5, 4]
heapq.heappush(arr, 3) # [1, 2, 3, 4, 5]
heapq.heappop(arr) # returns 1, arr becomes [2, 3, 4, 5]
arr[0] # Peek value 2
Using heapq as Max-Heap
Python only supports min-heaps natively. To create a max-heap, negate all values:
arr = [2, 1, 5, 4]
neg_arr = [-x for x in arr]
heapq.heapify(neg_arr) # [-5, -4, -2, -1]
heapq.heappush(neg_arr, -3) # [-5, -4, -3, -2, -1]
max_element = -heapq.heappop(neg_arr) # 5, neg_arr becomes [-4, -3, -2, -1]
peek_element = -neg_arr[0] # 4
Advanced Usage
You can also store tuples in a heap. They will be compared by their first element, then the second element, and so on.
This is useful for problems like “Top-K Elements in Array” where you might need to keep track of multiple properties.