Jump to content

4.1.2.4 Heaps (Min-Heap, Max-Heap)

From Computer Science Knowledge Base

4.1.2.4 Heaps: Finding the Biggest (or Smallest) Fast

Imagine a special pile of toys where the biggest toy is always at the very top, easy to grab. Or, imagine a pile where the smallest toy is always at the top. A heap in computer science is like that special pile! It's a tree-like data structure (but usually stored in a simple array) that helps you quickly find and grab the largest or smallest item.

Heaps have two main rules:

  1. It's a "complete binary tree," which means it's filled out level by level without any gaps, except possibly at the very last level, which is filled from left to right.
  2. It follows a "heap property":
    • In a Max-Heap, every parent node is larger than or equal to its children. So, the biggest item is always at the very top (the root).
    • In a Min-Heap, every parent node is smaller than or equal to its children. So, the smallest item is always at the very top (the root).

Heaps are super useful when you need to quickly find the "most important" item (either the biggest or smallest) from a collection, without having to sort the entire collection.

Min-Heap

In a Min-Heap, the smallest item is always at the very top (the root node). Every parent node is smaller than or equal to its children. This makes it super fast to find the smallest item in the entire heap.

  • Example: If you're managing a list of tasks and you always want to work on the task with the shortest time estimate first.

Max-Heap

In a Max-Heap, the largest item is always at the very top (the root node). Every parent node is larger than or equal to its children. This makes it super fast to find the biggest item in the entire heap.

  • Example: If you're managing a list of priorities and you always want to work on the task with the highest priority first.

Bibliography for Heaps

Retrieved from "https://wiki.omnivision.website/index.php?title=4.1.2.4_Heaps_(Min-Heap,_Max-Heap)&oldid=216"