Your Progress

16/30 completed

53% complete. Continue learning to master DSA!

Heaps and Priority Queues

Heaps are specialized tree-based data structures that satisfy the heap property, while priority queues are abstract data types that efficiently provide access to the element with the highest priority.

Key Takeaways

Heaps are complete binary trees that satisfy the heap property
Min-heaps have the smallest element at the root; max-heaps have the largest
Priority queues are commonly implemented using heaps
Operations like insertion and removal take O(log n) time
Heaps are used in heap sort, graph algorithms, and memory management

Understanding Heaps

A heap is a specialized tree-based data structure that satisfies the heap property:

Max Heap

In a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C.

Example:


        100
       /   \
     19     36
    / \    / \
   17  3  25   1

Min Heap

In a min heap, for any given node C, if P is a parent node of C, then the key of P is less than or equal to the key of C.

Example:


         1
       /   \
     3      5
    / \    / \
   6   4  13   10

Note: Heaps are complete binary trees, meaning all levels are completely filled except possibly the last one, which is filled from left to right.

Common Heap Operations

Insertion (O(log n))

To add an element to a heap:

Add the element to the bottom level of the heap at the leftmost open spot
Compare the added element with its parent; if they are in the correct order, stop
If not, swap the element with its parent and return to the previous step

This process is called "heapify-up" or "bubble-up".

Extract/Remove Top Element (O(log n))

To remove the top (maximum in max heap, minimum in min heap) element:

Replace the root with the last element in the heap
Remove the last element (which was just moved to the root)
Compare the new root with its children; if they are in the correct order, stop
If not, swap with the appropriate child (the larger one in a max heap, smaller in a min heap)
Repeat until the element is in the correct position

This process is called "heapify-down" or "bubble-down".

Peek (O(1))

Simply return the top element without removing it. This is a constant-time operation.

Build Heap (O(n))

Create a heap from an unsorted array by repeatedly applying heapify-down starting from the lowest non-leaf node up to the root.

Binary Heap Implementation

Binary heaps are commonly implemented using arrays, which provides memory efficiency and locality of reference:

Array Representation

For a node at index i:

Its left child is at index 2i + 1
Its right child is at index 2i + 2
Its parent is at index ⌊(i-1)/2⌋

JavaScript Implementation (Min Heap)

class MinHeap {
  constructor() {
    this.heap = [];
  }

  // Helper methods
  getLeftChildIndex(parentIndex) {
    return 2 * parentIndex + 1;
  }

  getRightChildIndex(parentIndex) {
    return 2 * parentIndex + 2;
  }

  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  hasLeftChild(index) {
    return this.getLeftChildIndex(index) < this.heap.length;
  }

  hasRightChild(index) {
    return this.getRightChildIndex(index) < this.heap.length;
  }

  hasParent(index) {
    return this.getParentIndex(index) >= 0;
  }

  leftChild(index) {
    return this.heap[this.getLeftChildIndex(index)];
  }

  rightChild(index) {
    return this.heap[this.getRightChildIndex(index)];
  }

  parent(index) {
    return this.heap[this.getParentIndex(index)];
  }

  swap(indexOne, indexTwo) {
    const temp = this.heap[indexOne];
    this.heap[indexOne] = this.heap[indexTwo];
    this.heap[indexTwo] = temp;
  }

  // Operations
  peek() {
    if (this.heap.length === 0) {
      return null;
    }
    return this.heap[0];
  }

  poll() {
    if (this.heap.length === 0) {
      return null;
    }
    
    const item = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return item;
  }

  add(item) {
    this.heap.push(item);
    this.heapifyUp();
    return this;
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    
    while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index);
    }
  }

  heapifyDown() {
    let index = 0;
    
    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      
      if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
      
      if (this.heap[index] < this.heap[smallerChildIndex]) {
        break;
      } else {
        this.swap(index, smallerChildIndex);
      }
      
      index = smallerChildIndex;
    }
  }

  size() {
    return this.heap.length;
  }
}

Priority Queues

A priority queue is an abstract data type where each element has a "priority" associated with it. Elements with higher priorities are served before elements with lower priorities.

Key Operations

insert(item, priority): Add an item with the given priority
getHighestPriority(): Return the highest priority element
deleteHighestPriority(): Remove and return the highest priority element

Priority Queue Implementation Using Min Heap

class PriorityQueue {
  constructor() {
    this.heap = [];
  }
  
  // Same helper methods as MinHeap...
  
  enqueue(value, priority) {
    this.heap.push({ value, priority });
    this.heapifyUp();
    return this;
  }
  
  dequeue() {
    if (this.heap.length === 0) {
      return null;
    }
    
    const item = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return item.value;
  }
  
  // Modified heapify methods to work with objects that have priority
  heapifyUp() {
    let index = this.heap.length - 1;
    
    while (
      this.hasParent(index) && 
      this.parent(index).priority > this.heap[index].priority
    ) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index);
    }
  }
  
  heapifyDown() {
    let index = 0;
    
    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      
      if (
        this.hasRightChild(index) && 
        this.rightChild(index).priority < this.leftChild(index).priority
      ) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
      
      if (this.heap[index].priority < this.heap[smallerChildIndex].priority) {
        break;
      } else {
        this.swap(index, smallerChildIndex);
      }
      
      index = smallerChildIndex;
    }
  }
  
  // Other methods same as MinHeap...
}

Time and Space Complexity

Operation	Time Complexity
Peek/Find Min/Max	O(1)
Insert	O(log n)
Delete Min/Max	O(log n)
Build Heap	O(n)
Heapify	O(log n)
Space Complexity	O(n)

The logarithmic time complexity for insertion and deletion operations makes heaps particularly efficient for priority queue implementations and algorithms that require repeatedly finding the minimum or maximum element.

Applications of Heaps and Priority Queues

Heap Sort

An efficient comparison-based sorting algorithm with O(n log n) time complexity that uses a heap data structure.

Dijkstra's Algorithm

Uses a priority queue to efficiently find the shortest path between nodes in a graph.

Prim's Algorithm

A greedy algorithm that finds a minimum spanning tree for a weighted undirected graph using a priority queue.

Huffman Coding

A data compression algorithm that uses a priority queue to build an optimal prefix-free encoding tree.

K Closest Points

Finding the k closest points to a given point efficiently using a max heap of size k.

Median Maintenance

Using two heaps (max and min) to efficiently keep track of the median of a stream of numbers.

Common Heap Problems

1. Kth Largest Element

Find the kth largest element in an unsorted array.

function findKthLargest(nums, k) {
  // Using min heap of size k
  const minHeap = new MinHeap();
  
  for (const num of nums) {
    minHeap.add(num);
    
    if (minHeap.size() > k) {
      minHeap.poll(); // Remove the smallest element
    }
  }
  
  return minHeap.peek(); // The top of the heap is the kth largest
}

2. Merge K Sorted Lists

Merge k sorted linked lists into one sorted linked list.

function mergeKLists(lists) {
  const minHeap = new MinHeap();
  
  // Add the first element from each list to the heap
  for (let i = 0; i < lists.length; i++) {
    if (lists[i]) {
      minHeap.add({
        val: lists[i].val,
        listIndex: i,
        node: lists[i]
      });
    }
  }
  
  const dummy = new ListNode(0);
  let current = dummy;
  
  // Process the heap
  while (minHeap.size() > 0) {
    const { val, listIndex, node } = minHeap.poll();
    
    // Add to result list
    current.next = new ListNode(val);
    current = current.next;
    
    // Add the next element from the same list
    if (node.next) {
      minHeap.add({
        val: node.next.val,
        listIndex: listIndex,
        node: node.next
      });
    }
  }
  
  return dummy.next;
}

Conclusion

Heaps and priority queues are powerful data structures that provide efficient solutions for a wide range of problems, particularly those requiring fast access to the minimum or maximum element. Their logarithmic-time operations make them indispensable tools in algorithm design and optimization.

Remember

When faced with problems involving finding the minimum/maximum element repeatedly, or maintaining a collection of elements ordered by priority, consider using a heap or priority queue for an efficient solution.

Next Steps

Now that you understand heaps and priority queues, explore these related topics:

Tree Traversal

Learn different ways to visit tree nodes

Shortest Path Algorithms

Explore Dijkstra's and other path-finding algorithms

Advanced Data Structures

Discover more complex data structures