Heap

Heap is a tree-like Data Structure optimized for quickly finding the highest or lowest priority item.

The most common heaps are:

• Min-heap: the smallest value is at the root
• Max-heap: the largest value is at the root

Heaps are commonly implemented using an array, where parent and child positions are calculated from indexes.

For a node at index i:

• Left child: 2i + 1
• Right child: 2i + 2
• Parent: (i - 1) / 2

Common operations:

• Peek minimum or maximum: O(1)
• Insert: O(log n)
• Remove minimum or maximum: O(log n)

Heaps are commonly used to implement priority queues.

flowchart TD
    One["1: min"] --> Three["3"]
    One --> Five["5"]
    Three --> Eight["8"]
    Three --> Nine["9"]

Anki

id: heap-definition deck: Computer Science::Data Structures tags: data-structures heap

Q: What question can a heap answer quickly? A: Which item has the smallest or largest priority?

id: heap-priority-queue deck: Computer Science::Data Structures tags: data-structures heap priority-queue

Q: Why is a heap useful for a task scheduler? A: It can quickly pick the next task with the highest or lowest priority.