Back to course

Lesson 34: Heaps: Max Heap and Min Heap structure

Algorithms: From Zero to Hero (A Beginner's Guide)

34. Heaps: Max Heap and Min Heap Structure

A Heap is a specialized tree-based data structure that satisfies the Heap Property.

Crucially, a Heap is usually implemented efficiently using an array.

Heap Properties

  1. Completeness: It must be a complete binary tree (all levels are fully filled, except possibly the last level, which is filled from left to right).
  2. Heap Order:
    • Max Heap: For every node, the value must be greater than or equal to the values of its children (The root holds the maximum element).
    • Min Heap: For every node, the value must be less than or equal to the values of its children (The root holds the minimum element).

Why are Heaps Useful?

Heaps are essential for implementing priority queues and for running algorithms like Heap Sort and Dijkstra's shortest path algorithm efficiently.

Operations like insertion and deletion of the root element (max/min) take O(log N) time.