Skip to main content

Deque and Priority Queue

TL;DR​

Deques support O(1) insertion and deletion at both ends, enabling problems like sliding window optimization and palindrome detection. Priority queues using heaps efficiently maintain k largest elements or dynamic ranking. Heaps guarantee O(log n) insertion/deletion while maintaining partial ordering. Two-heap approach finds running median in O(log n) per insertion. Understanding deques versus priority queues helps select optimal data structure for each problem's characteristics.

Core Concepts​

Double-Ended Queue Operations​

Deque structure allows adding/removing elements efficiently at both front and back. Implemented via circular buffer (array) achieving O(1) access and modification at both ends, or linked list offering memory flexibility.

Deque vs Queue vs Stack differs by access points. Queues use FIFO (one end in, other out). Stacks use LIFO (one end). Deques support both, making them versatile for problems requiring two-end access.

Circular buffer implementation uses fixed array with two pointers (front/rear). Adding at front or rear wraps indices modulo capacity. Offers cache efficiency but requires manual size management.

Linked list implementation uses doubly-linked nodes, adding at head/tail by updating pointers. More flexible with size but cache-unfriendly and requires extra memory per node.

Heap Structure and Properties​

Binary heap is complete binary tree in array form. Parent at index i has children at 2i+1 (left) and 2i+2 (right). Min-heap maintains parent ≤ children; max-heap maintains parent ≥ children.

Heapify operation restores heap property after insertion/deletion. Sift-up moves new element up while violating property; sift-down moves elements down. Both achieve O(log n) complexity.

Heap insertion appends element at end, then sift-up. O(log n) time. Heap deletion removes root, moves last element to root, then sift-down. O(log n) time.

Build heap from array iterates from last non-leaf node downward, sifting each. O(n) time, more efficient than n insertions.

Top-K Problems with Heaps​

Top-K largest elements uses min-heap of size k. Maintain heap of k largest; when encountering larger element, remove min and insert new. Final heap contains k largest in O(nlog k) time.

Top-K frequent elements first counts frequencies (hash map), then applies top-k algorithm. Heap comparator uses frequency. O(n + klog n) total.

KClosest points calculates distance, then applies top-k pattern. Points with larger distance replace minimum in heap.

Advantages versus sorting: sorting is O(n log n); heap approach is O(n log k) when k << n.

Running Median with Two Heaps​

Two-heap approach maintains max-heap for lower half and min-heap for upper half. Max-heap's root ≤ min-heap's root at all times.

Size balance keeps heaps within one element of each other. If size differs by 2, move root from larger to smaller heap.

Median calculation: if equal sizes, median is average of two roots; if unequal, median is larger heap's root.

Complexity achieves O(log n) insertion and O(1) median query, enabling efficient stream processing.

Key Algorithms and Techniques​

Deque with Circular Buffer​

Two-pointer system managing front/rear with modulo arithmetic for wraparound.

Heap Sift Operations​

Sift-up for insertion, sift-down for deletion, maintaining heap property.

Min-Heap for Top-K Largest​

Keep k largest in min-heap; remove min when new element larger appears.

Two-Heap Median Finding​

Balance max-heap and min-heap; maintain invariant that max-heap max ≤ min-heap min.

Practical Example​

import heapq
from collections import deque

# Deque operations
def deque_operations():
    """Demonstrate deque bidirectional access."""
    dq = deque([1, 2, 3])
    dq.appendleft(0)      # O(1)
    dq.append(4)          # O(1)
    dq.popleft()          # O(1)
    dq.pop()              # O(1)
    return list(dq)

# Top-K largest elements using min-heap
def top_k_largest(nums, k):
    """Find k largest elements using min-heap."""
    if k == 0:
        return []

    heap = nums[:k]
    heapq.heapify(heap)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)

    return sorted(heap, reverse=True)

# Top-K frequent elements
def top_k_frequent(nums, k):
    """Find k most frequent elements."""
    from collections import Counter

    count = Counter(nums)
    # Min-heap of (frequency, element)
    heap = [(-freq, num) for num, freq in count.items()]
    heapq.heapify(heap)

    result = []
    for _ in range(k):
        if heap:
            result.append(heapq.heappop(heap)[1])

    return result

# Running median with two heaps
class MedianFinder:
    def __init__(self):
        self.max_heap = []  # Max-heap (negate for Python's min-heap)
        self.min_heap = []

    def addNum(self, num):
        """Add number and maintain heaps."""
        # Add to max-heap (negate to simulate max)
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)

        # Balance heaps
        if len(self.max_heap) > len(self.min_heap) + 1:
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        elif len(self.min_heap) > len(self.max_heap):
            val = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -val)

    def findMedian(self):
        """Return current median."""
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2.0
        return float(-self.max_heap[0])

# Build heap in O(n)
def build_heap(arr):
    """Build heap from array."""
    heapq.heapify(arr)
    return arr

# Test cases
print(f"Deque ops: {deque_operations()}")
print(f"Top-3 largest in [1,2,3,5,6,4]: {top_k_largest([1,2,3,5,6,4], 3)}")
print(f"Top-2 frequent in [1,1,1,2,2,3]: {top_k_frequent([1,1,1,2,2,3], 2)}")

mf = MedianFinder()
for num in [1, 2, 3, 4, 5]:
    mf.addNum(num)
    print(f"Median after adding {num}: {mf.findMedian()}")

Common Pitfalls​

warning

Heap index formula errors: Left child at 2i+1, right at 2i+2. Using 2i or 2i+1 for both causes incorrect tree structure.

Forgetting to heapify after building: Simply placing elements in array doesn't create heap. Must call heapify to restore property.

Top-K min-heap confusion: Using max-heap for top-K largest wastes space. Min-heap of size k is optimal; remove min when larger appears.

Median heap balance forgotten: Two-heap median requires constant balancing. Skipping this produces incorrect results when sizes differ significantly.

Deque wraparound errors: Circular buffer indices must wrap with modulo. Forgetting wraparound causes array bounds errors.

Self-Check​

  1. Explain how min-heap finds top-K largest in O(n log k) time. Why is this better than sorting?
  2. Why do two heaps find running median efficiently? What invariant must hold?
  3. How does circular buffer implement deque? Why is modulo necessary?

One Takeaway​

info

Master deques for bidirectional access and priority queues (heaps) for efficient selection and ranking. Two-heap approach elegantly solves running median. Top-K problems showcase how choosing right data structure—heap over sorting—yields better complexity.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.