Queue • Advanced Architectures

Priority Queue (Heap Implementation)

While a Priority Queue is an Abstract Data Type (ADT), a Binary Heap is the concrete data structure that actually makes it fast.

The Array Heap

A heap is a Complete Binary Tree mathematically mapped to a standard 1D Array. For any node at index `i`, its left child is at `2i + 1`, and right child is at `2i + 2`.

O(log N) Push/Pop

When you insert an element, it is placed at the end of the array, then "Bubbles Up" to its correct position. When you pop, the max element is removed, the last element is moved to the top, and it "Sinks Down". Both take O(log N) time.

Why not sorting?

If you used a sorted array, inserting a new element would require shifting everything over, taking O(N) time. The Heap maintains just enough order to find the max in O(1) and extract it in O(log N).

Loading Lab...

Queue • Advanced Architectures

Priority Queue (Heap Implementation)

While a Priority Queue is an Abstract Data Type (ADT), a Binary Heap is the concrete data structure that actually makes it fast.

The Array Heap

A heap is a Complete Binary Tree mathematically mapped to a standard 1D Array. For any node at index `i`, its left child is at `2i + 1`, and right child is at `2i + 2`.

O(log N) Push/Pop

Why not sorting?

If you used a sorted array, inserting a new element would require shifting everything over, taking O(N) time. The Heap maintains just enough order to find the max in O(1) and extract it in O(log N).

Priority Queue Heap

Priority Queue Heap

Priority Queue (Heap Implementation)

The Array Heap

O(log N) Push/Pop

Why not sorting?

Priority Queue (Heap Implementation)

The Array Heap

O(log N) Push/Pop

Why not sorting?