Heap and Priority Queue: A Complete Guide to Building Trees with Arrays

This is part 2 of the data-structure series previewed at the end of the Stack and Queue article. The subject this time is the heap, but first we need to clear up a common misconception.

In the related article Stack and Queue: A Complete Guide, Including Why Swift Has No Stack Type (and the removeFirst Trap), you can review both the background concepts and the connected use cases.

The data-structure heap shares only its name with the memory heap and has nothing to do with it. The memory heap is a dynamically allocated region, while the heap discussed today is “a tree for retrieving the minimum (or maximum) in O(1) time.”

The differences between memory-allocation regions are explained separately in Stack vs. Heap. This article focuses only on the data-structure Heap and Priority Queue.

If you came here expecting the heap from the Stack vs. Heap article, this is a completely different world.

The problem a heap solves is straightforward.

“I want to process the most urgent item first, but sorting everything in advance feels wasteful.”

---

Sorting Is Overkill

Suppose we build a queue that removes the highest-priority task first. Sorting an array every time costs O(n log n) per insertion.

Even maintaining sorted order and finding the insertion point costs O(n) because elements must be moved.

But think about what we actually need: the entire collection does not have to be sorted. We only need to know the single most urgent item right now immediately.

It is not too late to identify second place after first place has been removed.

That is exactly the extent of a heap’s promise. As a result, both insertion and deletion finish in O(log n).

“The fewer guarantees you make, the faster you can be” is a classic trade-off in data-structure design.

---

Heap Rule: Parents Are Smaller Than Their Children—and That Is All

A min-heap is a complete binary tree with exactly one rule.

Every parent is less than or equal to its children.

The ordering among siblings does not matter. The left subtree does not need to be smaller than the right one.

Only parent-child relationships matter. Thanks to this looseness, the root always contains the global minimum, and nothing beyond that is guaranteed.

Insertion (sift up): Add the element at the very end, then swap it with its parent while it is smaller, moving upward. It moves only as far as the tree height, so it is O(log n).

Extracting the minimum (sift down): Remove the root, move the last element to the root, then swap it downward with the smaller of its two children. This is also O(log n).

---

The Magic of Building a Tree with an Array

This is where heap implementations become elegant. Because a complete binary tree is filled from left to right without gaps, it can be laid out sequentially in an array without pointers.(NIST Heap).

Index:  0   1   2   3   4   5
Value:     [1,  3,  2,  7,  4,  5]

Index calculations alone reveal the family relationships.

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

There are no node objects, child pointers, or heap-memory allocations. You retain the cache-locality benefits discussed in Array vs. Linked List while borrowing only the tree’s logical structure.

The skeleton in Swift looks like this.

struct MinHeap<Element: Comparable> {
    private var elements: [Element] = []

    var min: Element? { elements.first }   // O(1)

    mutating func insert(_ value: Element) {  // O(log n)
        elements.append(value)
        siftUp(from: elements.count - 1)
    }

    mutating func removeMin() -> Element? {   // O(log n)
        guard !elements.isEmpty else { return nil }
        elements.swapAt(0, elements.count - 1)
        let min = elements.removeLast()
        siftDown(from: 0)
        return min
    }
}

siftUp/siftDown are the repeated swaps described above.

For reference, build-heap, which turns an existing array into a heap, is not O(n log n) from inserting each element. Sifting down from the lower half finishes in O(n)—a detail that often appears in interviews.

---

Where Heaps Fit in Practice

A priority queue is a heap. Borrowing the Stack and Queue article’s wording, a queue removes items in arrival order, while a priority queue removes them in urgency order; a heap is its standard implementation (NIST Priority Queue).

• OS scheduler: Assigns CPU time to higher-priority processes first
• Dijkstra’s shortest path: An algorithm that repeatedly extracts “the shortest path found so far”—without a heap, performance collapses
• Timer management: An internal system structure where only the next timer to fire matters among many timers
• Heap sort: Insert everything and remove everything to obtain O(n log n) sorting. Its strength is in-place sorting without extra memory
• Top-K problems: “Keep the K largest items from a stream”—solve it in O(n log K) with a size-K min-heap. A coding-interview classic

The Swift standard library has no heap. Like the Deque in the Stack and Queue article, Apple’s swift-collections package provides Heap (swift-collections Heap).

This min-max heap implementation supports both min and max in O(log n). When external packages are unavailable, such as in coding tests, learning the MinHeap skeleton above is the practical choice.

---

Summary

• The data-structure heap shares only its name with the memory heap—it is “a tree that returns the minimum immediately”
• Its only rule is parent ≤ child—giving up full sorting buys O(log n) insertion and deletion
• As a complete binary tree, it can be laid out in an array without pointers—parent (i-1)/2, children 2i+1, 2i+2
• A heap is the standard implementation of a priority queue; Dijkstra, schedulers, and Top-K are representative applications
• In Swift, use Heap from swift-collections; in coding tests, implementing it yourself is standard

The next article covers hash tables: how Swift Dictionary achieves O(1), and what the requirements of Hashable really mean.

Sources and verification

• swift-collections HeapApple · Official documentation · Checked August 17, 2026Supports: Swift Heap API and min/max-heap behavior
• NIST Dictionary of Algorithms: Priority QueueNIST · Official data · Checked August 17, 2026Supports: Abstract data type definition of a priority queue
• NIST Dictionary of Algorithms: HeapNIST · Official data · Checked August 17, 2026Supports: Structure and operational characteristics of array-based heaps