Heap

What is a Heap? #

  • Tree-Based Data Structure: A heap is essentially a specialized binary tree (nearly complete – all levels filled except maybe the last, with nodes filled left to right).
  • Heap Property: A heap maintains a critical property:
    • Max Heap: The key (or value) of each node is always greater than or equal to the keys of its children. The root node has the largest value.
    • Min Heap: The key of each node is always less than or equal to the keys of its children. The root node has the smallest value.

Common Heap Operations #

  1. Insert (push):

    • Add the new element to the end of the heap (bottom of the tree).
    • “Bubble up” (or heapify up): Compare the new element with its parent. If it violates the heap property, swap them. Continue swapping upwards until the property is restored.

  2. Extract Max/Min (pop):

    • The root node holds the maximum (max-heap) or minimum (min-heap) value.
    • Remove the root and replace it with the last element in the heap.
    • “Bubble down” (or heapify down): Compare the new root with its children. If it violates the heap property, swap it with the larger (max-heap) or smaller (min-heap) child. Continue swapping downwards until the property is restored.

  3. Peek: Access the root element (maximum or minimum) without removing it.

Implementation #

Heaps are often implemented using arrays rather than explicit tree structures with pointers. This is due to the implicit structure of a complete binary tree:

  • Elements can be placed into an array level by level.
  • Parent and children indices can be calculated:
    • For an element at index i:
      • Parent: (i - 1) // 2
      • Left Child: 2 * i + 1
      • Right Child: 2 * i + 2

Time Complexity (Big O Notation)

  • Insert & Extract Max/Min: O(log n) due to the bubbling up/down operation (the height of a balanced tree is logarithmic).
  • Peek: O(1) (constant time)

Space Complexity

  • O(n) - where ’n’ is the number of elements in the heap.

Why Use Heaps? #

  • Priority Queues: Heaps are the natural choice to implement priority queues. Get the highest/lowest priority element efficiently.
  • Sorting: Used in the algorithm Heapsort.
  • Graph Algorithms: Often found in algorithms like Dijkstra’s shortest path.