Skip to content

Heaps & Priority Queues

  • Min Heap: A binary tree where each parent node is less than or equal to its children, ensuring that the minimum element is always at the root.
  • Max Heap: A binary tree where each parent node is greater than or equal to its children, ensuring that the maximum element is always at the root.
  • Heapfy: The process of converting an unordered array into a heap data structure, which can be done in O(n) time using the "sift down" method.
1
import heapq

graph TD
    N0[-4]
    N1[3]
    N2[1]
    N3[0]
    N4[2]
    N5[5]
    N6[10]
    N7[8]
    N8[12]
    N9[9]

    N0 --> N1
    N0 --> N2

    N1 --> N3
    N1 --> N4

    N2 --> N5
    N2 --> N6

    N3 --> N7
    N3 --> N8

    N4 --> N9
  • left(i) = 2*i + 1
  • right(i) = 2*i + 2
  • parent(i)= (i-1)//2
1
tree = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9]

Create a heap

1
2
heapq.heapify(tree)
tree

[-4, 0, 1, 3, 2, 5, 10, 8, 12, 9]

Heap push - insert an element into the heap while maintaining the heap property.

  • Time complexity: O(log n)
  • Space complexity: O(1)
1
heapq.heappush(tree, 4)

Heap pop - remove and return the root element (minimum for min heap, maximum for max heap) while maintaining the heap property.

  • Time complexity: O(log n)
  • Space complexity: O(1)
1
2
3
minimum = heapq.heappop(tree)

tree, minimum

([0, 2, 1, 3, 4, 5, 10, 8, 12, 9], -4)