See all coding puzzles and patterns here.

---

Data Structure Description

A heap is a tree-like data structure that satisfies the heap property, which states that for a min (max) heap, for every element $E$, if $P$ is a parent of the element, then $P$ is less (greater) than $E$.

There are several variants of heaps, but the most common are binary heaps, which can be and typically are implemented using just an array or list, by enforcing that for every index $i$, its direct children are $2i + 1$ and $2i + 2$, which satisfies the heap property if the elements at $2i + 1$ and $2i + 2$ are greater than the element at $i$. In particular, a sorted array already is a binary heap.

A heap can be considered a type of priority queue in which the comparison of items constitutes their relative priorities.

---

Interface

A min-heap (max-heap) has these these operations:

1. a constructor that can take an unsorted array of numbers,
2. a pop method that removes the lowest (highest) element while keeping the ordering in place,
3. an insert method that adds an element into the heap, and
4. an optional pop_push method that pops the lowest (highest) element and inserts a given element into the heap.

---

Binary Heap Performance Characteristics

Let $n$ equal the number of elements in the heap. Then runtime complexity should be:

• Insert: $O(log(n))$
• Pop: $O(log(n))$
• Insert all: $O(n \cdot log(n))$
• Pop all: $O(n \cdot log(n))$

---

Example MinHeap Implementation

class MinHeap(object):
    def __init__(self, items: list[int] = []):
        self.store = []
        for item in items:
            self.push(item)

    def push(self, item) -> bool:
        self.store.append(item)
        curr_idx = len(self.store) - 1
        parent_idx = MinHeap.get_parent(curr_idx)
        while parent_idx >= 0 and parent_idx < curr_idx and self.store[parent_idx] > self.store[curr_idx]:
            self.store[parent_idx], self.store[curr_idx] = self.store[curr_idx], self.store[parent_idx]
            curr_idx = parent_idx
            parent_idx = MinHeap.get_parent(curr_idx)

    @classmethod
    def get_left(cls, i: int) -> int:
        return (2 * i) + 1

    @classmethod
    def get_right(cls, i: int) -> int:
        return (2 * i) + 2

    @classmethod
    def get_parent(cls, i: int) -> int:
        return (i - 1) // 2

    def pop(self):
        if len(self.store) == 0:
            return None
        if len(self.store) == 1:
            return self.store.pop()
        res = self.store[0]
        self.store[0] = self.store.pop()
        curr_idx = 0
        while curr_idx < len(self.store):
            left_idx = MinHeap.get_left(curr_idx)
            right_idx = MinHeap.get_right(curr_idx)
            min_idx = curr_idx
            if left_idx < len(self.store) and self.store[left_idx] < self.store[min_idx]:
                min_idx = left_idx
            if right_idx < len(self.store) and self.store[right_idx] < self.store[min_idx]:
                min_idx = right_idx
            if min_idx == curr_idx:
                break
            self.store[curr_idx], self.store[min_idx] = self.store[min_idx], self.store[curr_idx]
            curr_idx = min_idx
        return res

    def pop_push(self, item):
        if len(self.store) > 0:
            if self.store[0] == item:
                return
            self.pop()
        self.push(item)

---

Puzzles

Puzzle	Difficulty	External Link
Find the Kth Largest Element	Medium	Leetcode 215
K Closest Points to Origin	Medium	Leetcode 973
Largest K Elements	Medium
Magic Candy Bags	Medium