Log In Sign Up
Day 17

Day 17: Heaps and Priority Queues

17/60 Days

Heaps and Priority Queues #

Welcome to Day 17 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Heaps and Priority Queues, powerful data structures that are essential for many efficient algorithms.

What is a Heap? #

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

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

The heap is one maximally efficient implementation of an abstract data type called a priority queue.

Types of Heaps #

  1. Max Heap: The root node has the largest value, and the property is maintained for all sub-trees.
  2. Min Heap: The root node has the smallest value, and the property is maintained for all sub-trees.

Implementing a Binary Heap in Python #

We’ll implement a min heap using a list in Python:

 1class MinHeap:
 2    def __init__(self):
 3        self.heap = []
 4
 5    def parent(self, i):
 6        return (i - 1) // 2
 7
 8    def left_child(self, i):
 9        return 2 * i + 1
10
11    def right_child(self, i):
12 …