Mastering Heaps and Priority Queues in C++: A Complete Guide for NIU CSCI 340 Assignment 9

Understanding Heaps: The Foundation of Efficient Priority Queues

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property. For a max-heap, the parent node is always greater than or equal to its children; for a min-heap, the parent is smaller. This property makes heaps ideal for implementing priority queues, where the highest (or lowest) priority element is always at the top. In the context of NIU CSCI 340 Assignment 9, you are tasked with building a heap from scratch using an array representation and then using it to create a priority queue class that mimics the STL std::priority_queue.

Think of a heap like a game leaderboard in a battle royale game: the top player (root) has the highest score, and as scores change, players bubble up or down to maintain the order. Similarly, in AI task scheduling, the highest priority task is always processed first. This tutorial will guide you through every function required in the assignment, with code examples and explanations.

Array Representation of a Complete Binary Tree

Instead of using pointers, we store the heap in an array by mapping nodes in level order. For a node at index i (0-based), its left child is at 2*i + 1, right child at 2*i + 2, and parent at (i-1)/2. The root is at index 0. This compact representation is memory-efficient and cache-friendly.

// heap.h
int heap_left(int node) { return 2 * node + 1; }
int heap_right(int node) { return 2 * node + 2; }
int heap_parent(int node) {
    if (node == 0) return 0;
    return (node - 1) / 2;
}

Heap Traversals: Preorder, Inorder, Postorder, Level-order

Traversals are essential for debugging and verifying the heap structure. The heap is a binary tree, so the recursive traversal functions are similar to those for binary trees, but using array indices.

Preorder Traversal

Visit the current node, then recursively traverse the left subtree, then the right subtree.

void heap_preorder(const std::vector<int>& heapdata, size_t heapnodes, int node, std::function<void(int)> fn) {
    if (node >= (int)heapnodes) return;
    fn(heapdata[node]);
    heap_preorder(heapdata, heapnodes, heap_left(node), fn);
    heap_preorder(heapdata, heapnodes, heap_right(node), fn);
}

Inorder Traversal

void heap_inorder(const std::vector<int>& heapdata, size_t heapnodes, int node, std::function<void(int)> fn) {
    if (node >= (int)heapnodes) return;
    heap_inorder(heapdata, heapnodes, heap_left(node), fn);
    fn(heapdata[node]);
    heap_inorder(heapdata, heapnodes, heap_right(node), fn);
}

Postorder Traversal

void heap_postorder(const std::vector<int>& heapdata, size_t heapnodes, int node, std::function<void(int)> fn) {
    if (node >= (int)heapnodes) return;
    heap_postorder(heapdata, heapnodes, heap_left(node), fn);
    heap_postorder(heapdata, heapnodes, heap_right(node), fn);
    fn(heapdata[node]);
}

Level-order Traversal

Simply iterate through the array from index 0 to heapnodes-1.

void heap_levelorder(const std::vector<int>& heapdata, size_t heapnodes, std::function<void(int)> fn) {
    for (size_t i = 0; i < heapnodes; ++i) {
        fn(heapdata[i]);
    }
}

Checking the Heap Property: is_heap

This function verifies that for every node (except leaves), the heap condition holds. For a max-heap, each parent must be greater than or equal to its children. Use the provided compare function.

bool is_heap(const std::vector<int>& heapdata, size_t nodes, std::function<bool(int,int)> compare) {
    for (size_t i = 0; i < nodes; ++i) {
        size_t left = heap_left(i);
        size_t right = heap_right(i);
        if (left < nodes && !compare(heapdata[i], heapdata[left])) return false;
        if (right < nodes && !compare(heapdata[i], heapdata[right])) return false;
    }
    return true;
}

Bubble Up and Bubble Down: The Core Operations

These are the heart of heap maintenance. Bubble up (also called sift-up) is used after insertion; bubble down (sift-down) is used after extraction or during heapify.

Bubble Up

Start from a given index and swap with parent as long as the heap property is violated. Returns the number of swaps performed.

int heap_bubble_up(std::vector<int>& heapdata, size_t nodes, int start, std::function<bool(int,int)> compare) {
    int swaps = 0;
    int current = start;
    while (current > 0) {
        int parent = heap_parent(current);
        if (compare(heapdata[parent], heapdata[current])) break; // correct order
        std::swap(heapdata[current], heapdata[parent]);
        current = parent;
        swaps++;
    }
    return swaps;
}

Bubble Down

Start from a given index and swap with the larger (max-heap) or smaller (min-heap) child until the heap property is restored.

int heap_bubble_down(std::vector<int>& heapdata, size_t nodes, int start, std::function<bool(int,int)> compare) {
    int swaps = 0;
    int current = start;
    while (true) {
        int left = heap_left(current);
        int right = heap_right(current);
        int target = current;
        if (left < (int)nodes && !compare(heapdata[target], heapdata[left])) target = left;
        if (right < (int)nodes && !compare(heapdata[target], heapdata[right])) target = right;
        if (target == current) break;
        std::swap(heapdata[current], heapdata[target]);
        current = target;
        swaps++;
    }
    return swaps;
}

Insertion and Extraction

Insert

Add the new key at the end of the array, increase the node count, and bubble it up.

void heap_insert(std::vector<int>& heapdata, size_t& nodes, int key, std::function<bool(int,int)> compare) {
    heapdata.push_back(key);
    nodes++;
    heap_bubble_up(heapdata, nodes, nodes-1, compare);
}

Extract

Remove the root (top priority), replace it with the last element, reduce node count, and bubble down from the root.

int heap_extract(std::vector<int>& heapdata, size_t& nodes, std::function<bool(int,int)> compare) {
    if (nodes == 0) throw std::out_of_range("Heap is empty");
    int top = heapdata[0];
    heapdata[0] = heapdata[nodes-1];
    nodes--;
    heapdata.pop_back();
    heap_bubble_down(heapdata, nodes, 0, compare);
    return top;
}

Heapify In-Place: Building a Heap from an Arbitrary Array

Two approaches: bottom-up (bubble down from the last non-leaf) and top-down (bubble up each element). Both are required.

Heapify In-Place Down (Bottom-Up)

void heapify_in_place_down(std::vector<int>& heapdata, size_t nodes, std::function<bool(int,int)> compare) {
    for (int i = (int)nodes/2 - 1; i >= 0; --i) {
        heap_bubble_down(heapdata, nodes, i, compare);
    }
}

Heapify In-Place Up (Top-Down)

void heapify_in_place_up(std::vector<int>& heapdata, size_t nodes, std::function<bool(int,int)> compare) {
    for (size_t i = 1; i < nodes; ++i) {
        heap_bubble_up(heapdata, nodes, i, compare);
    }
}

Heap Sort

Heap sort uses a max-heap to sort in ascending order. Extract the maximum repeatedly and place it at the end.

void heap_sort(std::vector<int>& heapdata, size_t nodes, std::function<bool(int,int)> compare) {
    // Build max-heap (using greater for max-heap)
    auto max_compare = [](int a, int b) { return a > b; };
    heapify_in_place_down(heapdata, nodes, max_compare);
    // Sort
    for (size_t i = nodes; i > 1; --i) {
        std::swap(heapdata[0], heapdata[i-1]);
        heap_bubble_down(heapdata, i-1, 0, max_compare);
    }
}

Building the Priority Queue Class

The heap_priority_queue class encapsulates the heap and provides a clean interface. It must support construction from a range of iterators, top(), empty(), size(), push(), and pop().

template <typename T, typename Container = std::vector<T>, typename Compare = std::less<T>>
class heap_priority_queue {
private:
    Container data;
    Compare comp;
    size_t num_nodes = 0;
public:
    // Constructor from iterator range
    template <typename InputIterator>
    heap_priority_queue(InputIterator first, InputIterator last) : data(first, last), num_nodes(std::distance(first, last)) {
        heapify_in_place_down(data, num_nodes, comp);
    }

    const T& top() const {
        if (empty()) throw std::out_of_range("Priority queue empty");
        return data[0];
    }

    bool empty() const { return num_nodes == 0; }
    size_t size() const { return num_nodes; }

    void push(const T& value) {
        heap_insert(data, num_nodes, value, comp);
    }

    void pop() {
        heap_extract(data, num_nodes, comp);
    }
};

Real-World Analogy: AI Task Scheduling

Imagine an AI assistant that manages multiple tasks: responding to user queries, running background computations, and fetching data. Each task has a priority. The priority queue ensures the highest-priority task is always executed next. When a new urgent task arrives (like a user interrupt), it is inserted and bubbles up to the top. This is exactly how your heap implementation works.

Common Pitfalls and Tips

• Off-by-one errors: Remember that array indices start at 0. The last non-leaf node is at n/2 - 1.
• Comparison function direction: For a min-heap, use std::less (or parent < child). For max-heap, use std::greater.
• Iterator ranges: The constructor expects two iterators representing the range [first, last). Use std::distance to get the size.
• Testing: Use the provided test harness or write your own to verify each function.

Conclusion

Implementing a heap and priority queue from scratch deepens your understanding of data structures and algorithms. This assignment covers essential operations that appear in real-world applications like operating system schedulers, network routers, and AI systems. By following this guide, you will have a solid foundation to complete NIU CSCI 340 Assignment 9 successfully.