Heaps

The case study for heaps begins with a need for sorted collections. This section illustrates implementing a simple priority queue ADT with a heap. The priority queue is exactly what it sounds like; a queue with additional logic that determines some form of ordering, or priority. You can implement a priority queue easily with an unsorted list, but finding (and removing) the min (or the max) value (priority) takes O(n) time. You can alternatively use a sorted list, which results in O(1) operations to find the min or max element, but insertion still takes O(n) time, meaning that priority queue construction takes O(n^2) time. Enter the heap structure. Properly designed heaps allow you to create a priority queue from a sequential structure in O(n) time, and add or remove elements in O(log(n)) time, making it more efficient overall than using lists when implementing basic priority queues.

The Heap ADT

Heaps are a special kind of tree with two specific additional properties:

1) The Heap-Order Property:

Each parent is either >= to its children (max heap), or <= to its children (min heap). This importantly only applies to parent-child relationships. Additionally requiring sibling order is a property of binary search trees (BSTs).

The heap-order property says that heaps are ordered, but this does not necessarily imply total ordering, or a sorted invariant. Consider the following min (binary) heap:

          3
        /    \
       5      9
     /  \    /  \
    8   12  11  14

Notice that each node is larger than its parent. This heap-order property only holds for parent-child relationships. For example, notice that first level after the head includes members 5 and 9, but node 5 includes a child that its smaller (8) than its own sibling (9). That is to say that the ordering doesn’t necessarily extend to each level, just to the localized parent-child relationship. In this way the heap is said to be (partially) ordered, but not sorted.

2) Complete Tree Property:

Each node contains the maximum number of children possible, and remaining nodes at level h reside in the left-most position.

The complete tree property directly affects the heap’s efficiency characteristics. Consider the following variation of the same set of information as the example in the heap-order property section:

         3
        /
       5
      / \
     8   9
        / \
       11 12
       /
      14

Technically speaking, this example represents the same information as the original example. However, the number of checks you need to perform to find a value increases with the height of the heap. Additionally, without guaranteeing that you’d populate the left-most child first, you effectively double the number of child checks for nodes with only one child. Indeed if you extend this example out to its logical conclusion you’d end up with a sorted list! That would spoil all the asymptotic advantages of the heap.

Heap Types

The previous section does not explicitly state the number of children for each heap node. Binary heaps represent the most common implementation of a heap. Binary heaps are heaps with only two children per parent. The association between heap and binary heap is so pervasive that most people define heaps as binary heaps. Ternary heaps (3-heap), quaternary heaps(4-heaps), etc. also exist, and are referred to more generally as d-ary heaps.

Heaps represent a maximally efficient implementataion of the basic priority queue ADT. Indeed the relationship is so strong that the two terms are often used interchanteably, regardless of the actual implementation of a priority queue. The heap name itself comes from a visualization of the hierarchical structure. The root, e.g. the highest priority item, is always at the “top of the heap”.

Tip

The term “heap” is overloaded. The heap data structures described here is not the same thing as a program’s (or system’s) heap memory structure.

The original example diagram uses a single value to represent each node, but often a heap uses some associative map for each of its nodes; one value to determine the data, and one value to determine the priority. Consider the following evolution of the original diagram:

                        (3, Peter)
                    /                \
            (5, Sleve)             (9, Bobson)
           /          \            /         \
    (8, Dichael) (12, Damiel) (11, Cork) (14, Flank)

This represents the same partial ordering (priority), but now each node contains an arbitrary value, in this case a name.

Implementations

This section covers how to make heap go brrr.

Sifting

The key to building and maintaining a heap is sifting operations. Sifting operations restore heap properties after insertions or removals in the backing structure. These operations are sometimes referred to as bubbling, percolating, or swimming, depending on the direction and context. This text uses the term sifting because it applies to both upward and downward movement through the heap, unlike bubbling, which is typically associated only with upward motion.

There are two primary sifting operations, sift up and sift down.

Sift Up

Sift up operations are used for node insertions. When you add a node to a heap you do so at the last spot in the backing array. From there you sift the node upwards in the tree to an appropriate spot that satisfies the heap order property. The sift up operation takes the heap itself and the index for the node you’re sifting up, which changes as its swapped in the tree.

    fn sift_up(&mut self, mut index: usize) {
        // Only sift up if the element is not the root (index 0)
        while index > 0 {
            // Calculate the parent's index
            let parent_index = (index - 1) / 2;

            // Perform comparisons to determine the swap target
            // NOTE: Switch < to > for max heap
            if self.arena[index] < self.arena[parent_index] {
                self.arena.swap(index, parent_index);
                // Move up to the parent's old position to continue sifting
                index = parent_index;
            } else {
                break; // No-op, heap is heapy 🍃🧘
            }
        }
    }

Sift Down

The most fundamental use for sift down operations occur when you remove an element from the heap. Rembmer that when you remove the “next” value from a heap (min value for a min heap, max value for a max heap) you do so from the heap’s root. When you remove the root node you initially swap in the last item in the heap which maintains the complete tree property. From there you need to sift the new root node down to a spot that maintains the heap order property. The sift down operation takes the heap itself and the index for the node you’re sifting down. Clever readers might ask Why not hard-code the starting index to zero and omit it as an argument if you’re always starting at the root? The short answer is that the heapify operation (covered in the next section) needs to perform this sift operation for more than just the root node, meaning that removals aren’t the only place where sift down operations are used.

    fn sift_down(&mut self, mut index: usize) {
        loop {
            // Calculate the index's children
            let left_child = 2 * index + 1;
            let right_child = 2 * index + 2;
            let mut target = index;

            // Perform comparisons to determine the swap target
            // NOTE: Switch < to > for a max heap
            if left_child < self.arena.len()
                && self.arena[left_child] < self.arena[target] {
                target = left_child;
            }
            if right_child < self.arena.len()
                && self.arena[right_child] < self.arena[target] {
                target = right_child;
            }

            if target != index {
                self.arena.swap(index, target);
                index = target;
            } else {
                break; // No-op, heap is heapy 🍃🧘
            }
        }
    }

Heap Construction & Floyd’s Algorithm

There are two common to build a heap from a sequential structure. The simplest way to build a heap is to use n number of push() operations to create a heap from a list of entries. Assuming each push() operation runs in O(log(n)) time, this simple approach results in O(n * log(n)) heap construction. This might be the only way to construct a heap from a linked list, but if you build a heap from an indexed structure, you can simply “heapify” it “from the bottom” in place in O(n) time.

The “heapify” or “bottom-up” construction, otherwise known as Floyd’s algorithm, works by applying a down_sift() operation to all non-leaf nodes in the backing structure, starting from the lowest non-leaf level (the level just above the leaf nodes) and progressing to the heap’s root. This works by assuming the input collection of non-null elements already represents a complete binary tree. You only need to apply the process to non-leaf nodes because each single element already satisfies both of the heap properties, so you can skip them entirely. To find the first non-leaf node in a complete binary tree H you start at index H[(n/2) - 1] (for a 0-indexed list/heap). From there, simply work your way through all indexes, sifting down each node, until you get to the root.

In Rust, this might look something like the following:

    pub fn from_slice(list: &[T]) -> Self
        where T: Clone {
        let mut heap = BinHeap::new();
        heap.arena = Vec::from(list);
        let start = (list.len() / 2).saturating_sub(1);
        for i in (0..=start).rev() {
            heap.sift_down(i);
        }
        heap
    }

    pub fn from_vec(list: Vec<T>) -> Self {
        let size = list.len();
        let mut heap = BinHeap { arena: list, size };
        let start = (size / 2).saturating_sub(1);
        for i in (0..=start).rev() {
            heap.sift_down(i);
        }
        heap
    }

The entire “heapify” process requires roughly n/2 number of sift_down() operations, which each take at worst O(log(n)) time. On the surface, this may appear like an n/2 * log(n) = O(n * log(n)) operation, but in reality, most of the operations are single swaps. Indeed only a few complex log(n) operations are performed near the top of the heap, so it can be said that the average expected temporal cost of a heapify operation is O(n). The true operational (temporal) cost is Σ (k=1 to log(n)) ( (n / (2^k)) * k ), if you want to get pedantic.

The Priority Queue ADT

Priority queues are a sorted type that impose comparative logic to a collection of sequentially ordered nodes. In a priority queue, you enqueue elements that get “sifted” or “bubbled” up, either logically, or physically within the backing structure’s storage layout, according to their priority. Elements also get dequeue’d according to their priority. To extend the food service analogy from the top of the page, some people in the line to order food may simply be there to pick up orders that they called in ahead of time, and perhaps the restaurant serves seniors first. This priority logic extends the “first come, first served” queuing logic.

The ADT model is defined by the following operations:

• enqueue(e) / enqueue(k, e) Adds an entry e to the queue; Either e must be comparable, or you must supply an additional parameters as a comparable key k to determine the element’s priority
• min() / peek() Returns, but does not remove, an entry with the lowest/highest priority
• remove_min() / dequeue() Returns and removes an entry with the lowest/highest priority value
• size() Returns the number of elements in the queue
• is_empty() Returns a Boolean indicating whether the list is empty

Adaptable Priority Queues

The adaptable priority queue adds the ability to mutate elements in the queue. Due to the level of control, its common to define APIs that separate the element’s data from its priority. For example, if you have a basic enqueue(k, e), you also include a set_element(eold, enew) operation to change an element’s data based on an internal find(e) operation. You can also add a set_priority(k, e) operation to change an element’s priority key.

Priority queues are probably the most difficult types to classify in this entire module. From the outside, they operate like lists with specific queuing logic, but internally may be composed of more advanced structures that separate them from simple list abstractions. For example, fully featured adaptable priority queue APIs often exhibit keyed structuring (covered in the next chapter), and under the hood, may include a combination of keyed and hierarchical structures to retain optimal performance characteristics. For this reason they are most appropriately categorized as composite types, and provide a good introduction to keyed structures, hierarchical structures, and sorting in general which are covered in the next two chapters.

(## Adaptable Priority Queues Keen readers will by now have noticed that this site contains both this Heaps page and a separate Priority Queues page under the Composite Structures module. This page asserts that heaps represent the maximally efficient implementation of a priority queue, so why are there two pages? The reason is that in the “real world” (calm down, Neo) you may want to change an arbitrary node’s priority or even remove it all together. So far, this section has dealt with simple heap ordering by implementing some comparator on the insertion object. Insertion objects may be arbitrarily complex to include separate ordering values and internal data values. Additionally, more advanced implementations require some efficient way to track elements in the heap without O(n) traversal operations. As a result, adaptable priority queues require a composite implementation which uses heaps as the basic data storage container along with an associative structure (usually a kind of map which are covered in a subsequent module) to provide efficient node lookups. As it turns out, priority queues are one of the more common structures used in real world problem solving, so the material is split to accommodate basic and more advanced implementations.)

Representation

All priority queues require some defined logic to compare entries in a meaningful way. The comparison logic you choose must define a total (linear) ordering scheme. Adaptable priority queues are more common due to their ability to mutute elements and priorities, so its generally common to use elements as key-value pairs and only impose total ordering on the element’s key.

Naive priority queues can be represented with lists, resulting in O(1) insertions by simply appending the list, and dequeuing operations that require O(n) time because each element must be read to determine the min/max in an unsorted list. You can also maintain a sorted invariant, but this is theoretically more expensive because inserts would become O(n) and you could dequeue the tail in O(n) time, but there are almost always more enqueue than dequeue operations in use. For this reason, priority queues are introduced in the sequential structures chapter.

However, the most efficient priority queues enqueue and dequeue elements in O(log(n)) time. These operations rely on sorted data structures not yet covered. Specifically, you can use a heap data structure for basic O(log(n)) operations, or couple the heap with a map fto retain those operational optimizations with a fully featured adaptable priority queue.

The element’s key determines the priority by which the element is placed instead of its insertion order. It is common for keys to be numbers, but any comparable object may be used as a key. Canonically the minimal key represents the highest priority. You may have heard this same logic extend in business operations where “priority zero” agendas represent the most urgent tasks. The priority queue ADT allows for multiple keys of the same priority value. If multiple elements contain equivalent keys the list’s operations may return arbitrarily ordered elements with the same key.

To implement an ordering scheme in Java you can use the Comparator or Comparable interfaces, and in Rust you can use the PartialOrd and Ord traits. The biggest difference are that only Comparable (Java) and Ord (Rust) ensure total ordering of types, whereas Comparator and PartialOrd may require additional constraints to ensure total ordering of key types. If your types have a “natural order” (such as integers) these may be easily derived, but in general partial ordered types may require more involved rule definitions to ensure total ordering of types for your structure. For example, types like Strings (and UUIDs) satisfy the Ord trait in Rust, but floating point types do not.

Once you have your keys figured out you’ll need to figure out how to implement the base structure of the queue. A priority queue is just a list right? Why not use one of the (many) list implementations already covered? Indeed this is all of a sudden sounding very similar to the focus of the Fundamental Structures module. Before getting too far ahead of yourself, consider the following base structure analysis. The details are for the Rust language and uses the Vec type for array-based list structures, but results will be very similar across languages.

• Unsorted array-based list (UAL): enqueue(k, v): O(1) Add the entry to the end of the list remove(k, v) / pop(): (min or max) O(n) The actual removal is O(1), but shifting elements requires O(n) min() / max(): O(n - 1) Because each entry must be compared size(): O(1) Checks the base list property assuming you’re using an off-the-shelf array-based implementation like an ArrayList or Vec

• Sorted array-based list (SAL): enqueue(k, v): O(n) Finding the correct insertion point and shifting elements is O(n) remove(k, v) / pop() (min or max): O(1) If the target removal entry is at the end of the list min() / max(): O(1) The min/max is the head/tail of the list size(): (Same as UAL)

• Unsorted linked list (ULL): enqueue(k, v): O(1) Simply add the entry at one of the ends of the list remove(k, v) / pop(): (min or max) Linked list removals are O(1), but getting to the right spot takes O(n) time min() / max(): O(n - 1) Because each entry must be compared size(): O(n) The operation must traverse the entire list, unless you maintain a counter which would make this a O(1) operation

• Sorted (doubly-) linked list (SLL): enqueue(k, v): Navigating to the correct insertion point is O(n) remove(k, v) / pop() (min or max): O(1) The target removal entry is either the head or tail of the list min() / max(): O(1) The min/max is the head/tail of the list size(): (SAme as ULL)

Operation	UAL	SAL	ULL	SLL
enqueue(k, v)	O(1)	O(n)	O(1)	O(n)
dequeue(k, v)	O(n)	O(1)	O(n)	O(1)
min()/max()	O(n - 1)	O(1)	O(n - 1)	O(1)
size()	O(1)	O(1)	O(1)	O(1)
is_empty()	O(1)	O(1)	O(1)	O(1)

Notice that there is pretty even tradeoff between enqueue and dequeue operations across the considered implementations. Given that both operations will likely happen at a ratio close to 1:1, the general convenience and performance of an array-based implementation probably eeks out the competition here, though there is no real big difference.

The following snippet illustrates a simple Vec-based implementation of the priority queue structure. Only code snippets are provided here. See the project’s repo for details. The queue itself exists as a struct with a single data field. Each data entry contains an Entry<K, V> type. This is a very simple example, so the most notable operation is the O(n) enqueue() operation which provides sorting logic. Notice that this operation actually wraps the Vec::insert() method which itself runs in O(n) time to shift remaining values to make room for the inserted value.

pub struct Entry<K, V> {
    key: K,
    value: V,
}

   ...

pub struct SortedVecQueue<K, V> {
    pub data: Vec<Entry<K, V>>
}

   ...

impl<K, V> PriorityQueue<K, V> for SortedVecQueue<K, V>
where K: Ord {

    type Entry = Entry<K, V>;

    //NOTE: Provides a wrapper for Vec::enqueue() which runs in O(n) time
    fn enqueue(&mut self, key: K, value: V) -> Result<(), Box<dyn std::error::Error>> {
        if Self::check_key(&key) {
            let mut insertion_index = self.data.len();
            // Finds the correct insertion index
            for (i, e) in self.data.iter().enumerate() {
                if key >= e.key {
                    insertion_index = i;
                    break;
                }
            }
            let entry = Entry::new(key, value);
            self.data.enqueue(insertion_index, entry); // Actually calls Vec::enqueue()
            Ok(())
        } else {
            Err("Invalid key".into())
        }
    }

   ...

This example test illustrates how the list can be used.

#[test]
pub fn example() {
    use crate::lists::queues::priority_queue::sorted_list::{
        PriorityQueue,
        SortedVecQueue
    };

    // Instantiates new list, declares the K and V types
    let mut list: SortedVecQueue<usize, &str> = SortedVecQueue::new();

    // Pushes a bunch of values with an associated key priority to the list
    list.enqueue(3, "Peter").ok();
    list.enqueue(5, "Bobson").ok();
    list.enqueue(2, "Brain").ok();
    list.enqueue(4, "Dingus").ok();
    list.enqueue(6, "Dorkus").ok();

    // Checks that the list is taking entries properly,
    // and that the peek() operation matches expectations
    assert_eq!(list.size(), 5);
    assert_eq!(list.peek(), Some("Brain").as_ref());

    // Creates a "sorted" list of dequeued items
    let mut queue: Vec<&str> = Vec::new();
    // Using the while loop avoids having to deal with partial moves in a for loop
    while !list.is_empty() {
        if let Some(v) = list.dequeue() {
            queue.push(v)
        }
    }

    // Checks that the final result of the queue logic is correct
    assert_eq!(queue, vec!["Brain", "Peter", "Dingus", "Bobson", "Dorkus"])

}

But what if there was a better way? What if you weren’t satisfied with trading linear and constant time for enqueue and dequeue operations? The good news is that you don’t have to! You can actually implement this structure with a heap to provide enqueue and dequeue operations that run in O(n log(n)) time. Heap structures are technically trees, but it is possible to implement binary heaps relatively easily with an array-based structure. Best of both worlds! Though not strictly required, you can sort a heap with heap sort in O(n * log(n)) time. What is the benefit over O(1)/O(n) options on sorted lists? Using a binary heap allows for enqueue and dequeue operations that require O(log n) time, so the amortized costs pay dividends. Fancy!

Introduction to Sorting

The study of heaps, and specifically the “heapify” algorithm, provides a natural segue into sorting. This is because heap sort provides a theoretically efficient algorithm. Heap sort guarantees O(n * log(n)) time complexity with the added advantage of being performed “in-place”, e.g. requiring no additional memory beyond the input array. In practice, however, heap sort often underperforms compared to algorithms like merge sort and quick sort. While those may use more memory (especially merge sort), they tend to make fewer comparisons and swaps, benefit from better cache locality, and are often faster on large datasets. As a result, merge sort and quick sort are more commonly used in real-world applications, despite heap sort’s strong theoretical properties.