Heaps and Priority Queues

1. What is a Priority Queue?

You're familiar with a standard queue, which operates on a "First-In, First-Out" (FIFO) principle. A priority queue is different. Instead of serving elements based on their arrival time, it serves them based on their priority.

A priority queue is an abstract data type with two main operations:

• Enqueue (Insert): Add an element to the queue with an associated priority.
• Dequeue (Extract): Remove the element with the highest priority from the queue.

If multiple elements share the same highest priority, they are typically served in the order they were added.

You could implement a priority queue with a simple list, but it would be inefficient. A heap is the ideal data structure for this job because it provides a great balance of performance for both insertion and extraction.

As you saw in the article, a Binary Heap provides $O(\log n)$ time for both insertion and deletion, making it far more efficient than a linked list or an unsorted array for a large number of elements.

2. The Heap Data Structure

A heap is a specialized binary tree that satisfies two key properties:

1. Heap Property: For a Max-Heap, the value of any parent node is greater than or equal to the values of its children. This ensures the largest element is always at the root. For a Min-Heap, the parent's value is less than or equal to its children's values, keeping the smallest element at the root. We will focus on the Max-Heap.

2. Completeness Property: A heap must be a complete binary tree. This means all levels of the tree are fully filled, except possibly for the last level, which is filled from left to right without any gaps.

The following video provides an excellent introduction to these concepts.

Array Representation

The 'completeness' property is brilliant because it allows us to represent a heap compactly in an array, without needing pointers like in other tree structures. The mapping is done by level-order traversal.

For a node at index i in the array:

• Its parent is at index: (i - 1) // 2
• Its left child is at index: 2 * i + 1
• Its right child is at index: 2 * i + 2

This array-based storage is key to the heap's efficiency.

3. Core Heap Operations

To use a heap as a priority queue, we need to be able to insert elements and extract the maximum element while maintaining the heap properties. This is done with two main procedures: sift-up and sift-down.

Insertion and the Sift-Up Operation

When we insert a new element, we must preserve both the completeness and the heap property.

1. Maintain Completeness: Add the new element to the first available spot, which is at the end of the array. The tree is still complete.
2. Restore Heap Property: The new element might be larger than its parent, violating the max-heap property. To fix this, we sift it up the tree. We compare the new element with its parent and swap them if the child is larger. We repeat this process until the element reaches the root or its parent is larger than it.

Extracting the Maximum and the Sift-Down Operation

The maximum element in a max-heap is always at the root (index 0). Extracting it is also a two-step process.

1. Remove the Root: To avoid leaving a hole at the root, we swap the root element with the last element in the heap. Then, we can simply pop the last element off the array. The tree is now smaller but still complete.
2. Restore Heap Property: The new root (the old last element) is likely much smaller than its children, violating the max-heap property. To fix this, we sift it down. We compare the new root with its children and swap it with the larger of the two. We repeat this process until the element is larger than both its children or it becomes a leaf node.

The following video visually demonstrates both the insertion (sift-up) and extraction (sift-down) operations.

Because the height of a complete binary tree with n nodes is $\log n$, both the sift-up and sift-down operations take at most $O(\log n)$ time.

4. Implementation: A Heap-Based Priority Queue

Now let's put it all together into a Python class. Our MaxHeap class will effectively be a max-priority queue.

• insert(item) will correspond to enqueue.
• extract_max() will correspond to dequeue.

class MaxHeap:
    def __init__(self):
        # Initialize an empty list to store the heap elements.
        self.heap = []

    def _parent_index(self, i):
        return (i - 1) // 2

    def _left_child_index(self, i):
        return 2 * i + 1

    def _right_child_index(self, i):
        return 2 * i + 2

    def _swap(self, i, j):
        """Swaps two elements in the heap."""
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def _sift_up(self, i):
        """Moves an element up to its correct position."""
        parent = self._parent_index(i)
        # While the node is not the root and is greater than its parent
        while i > 0 and self.heap[i] > self.heap[parent]:
            self._swap(i, parent)
            i = parent
            parent = self._parent_index(i)

    def _sift_down(self, i):
        """Moves an element down to its correct position."""
        max_index = i
        size = len(self.heap)

        while True:
            left = self._left_child_index(i)
            right = self._right_child_index(i)
            
            # Check if left child exists and is greater than current max
            if left < size and self.heap[left] > self.heap[max_index]:
                max_index = left

            # Check if right child exists and is greater than current max
            if right < size and self.heap[right] > self.heap[max_index]:
                max_index = right
            
            # If the largest element is still the current node, we're done
            if i == max_index:
                break
            
            self._swap(i, max_index)
            i = max_index

    def insert(self, value):
        """Inserts a new value into the heap (enqueue)."""
        self.heap.append(value)
        self._sift_up(len(self.heap) - 1)

    def extract_max(self):
        """Removes and returns the maximum element (dequeue)."""
        if not self.heap:
            return None

        size = len(self.heap)
        if size == 1:
            return self.heap.pop()

        # Swap root with the last element
        self._swap(0, size - 1)
        max_value = self.heap.pop()
        
        # Restore the heap property from the root
        self._sift_down(0)
        
        return max_value
    
    def peek_max(self):
        """Returns the maximum element without removing it."""
        return self.heap[0] if self.heap else None

# --- Let's test our Priority Queue ---
pq = MaxHeap()

# Insert elements (enqueue)
print("Inserting 45, 20, 14, 12, 31...")
pq.insert(45)
pq.insert(20)
pq.insert(14)
pq.insert(12)
pq.insert(31)

print("Heap array after insertions:", pq.heap)
print("Highest priority element (peek):", pq.peek_max())

# Extract max element (dequeue)
print("\nExtracting max:", pq.extract_max())
print("Heap array after extraction:", pq.heap)
print("New highest priority element:", pq.peek_max())

print("\nInserting 50...")
pq.insert(50)
print("Heap array after inserting 50:", pq.heap)
print("New highest priority element:", pq.peek_max())

print("\nExtracting max:", pq.extract_max())
print("Extracting max:", pq.extract_max())
print("Final heap array:", pq.heap)

Conclusion

Congratulations on completing the "Core Data Structures" module! You have now implemented a heap and used it to build a priority queue, one of the most useful applications of this data structure.

Key Takeaways:

• A Priority Queue is an abstract data type that serves elements based on priority, unlike a standard FIFO queue.
• A Heap is the most efficient data structure for implementing a priority queue, offering $O(\log n)$ time for both insertions and extractions.
• A heap must satisfy the heap property (max or min) and be a complete binary tree.
• The completeness property allows a heap to be efficiently stored in an array.
• Insertion uses a sift-up operation, and extracting the max/min uses a sift-down operation to maintain the heap properties.

Preview of the Next Lesson:

You've built a strong foundation in data structures. Now it's time to use them to solve problems. Our next module, "Algorithms: Sorting, Searching, and Design," will focus on fundamental algorithmic techniques. In the very first lesson, we will start with the basics of searching: you will implement linear search and binary search algorithms and analyze their complexities. This will be your first step into the world of algorithm design and analysis.