Heap

Abstract

---

• A Tree based structure that satisfies the Heap Invariant

Important

Heap forms the classical underlying Data Structure for Priority Queue.

There are many types of heaps we could use to implement a priority queue, such as binary heaps, Fibonacci heaps, binomial heaps, and pairing heaps. However, we usually use binary heaps due to their simplicity.

Heap Invariant

• Also known as Heap Property
• If node $A$ is a parent of node $B$, then $A$ is ordered with respect to $B$. This parent-child ordering relationship holds true for every pair of nodes within the heap
• In a max heap, the value of a parent node is always greater than or equal to the values of its child nodes. Conversely, in a min heap, the value of a parent node is always less than or equal to the values of its child nodes

Binary Heap

• A complete binary tree that supports heap invariant

References

---

• Priority Queue Introduction - YouTube
• Priority Queue Inserting Elements - YouTube