# Exploring Heaps: From Basics to Practical Applications in 30 Days

Written on

## Understanding Heaps and Their Importance

Heaps function similarly to queues but come with added advantages. Unlike queues, where items cannot have varying priorities and must be dequeued sequentially, heaps allow for prioritization. This capability is crucial in scenarios where certain items need to be prioritized over others.

For instance, imagine an investment platform that generates new investments daily at 9:00 a.m. based on an automated investment strategy. In this setup, individuals with larger portfolios are prioritized over those with smaller ones, irrespective of when they submit their investment strategies. Thus, the order in which these strategies are processed depends on portfolio size, highlighting the utility of heaps.

### What Are Heaps?

Heaps are commonly represented as trees, yet in programming, they are typically implemented using lists (or arrays). This article will focus on array-based heaps.

### Types of Heaps

There are two main types of heaps: min-heaps and max-heaps. While they are quite similar, the key distinction lies in their structure. In a min-heap, the smallest values are at the top (highest priority), whereas in a max-heap, the largest values occupy the top position. This article will concentrate on min-heaps.

### Min-Heap Characteristics

In a min-heap, items are not strictly ordered; they are added from left to right. This arrangement will be elaborated on shortly.

### How to Access Parent and Child Nodes

In a heap, the index of an element is denoted by the letter 'i'. Since heaps are implemented as lists, accessing the first or last element is straightforward, as is adding or removing items from either end.

### Heap Operations: Heapify Up

When adding an item to a heap, it is first placed in the last position, followed by a process known as "heapify up."

**Placement**: The new element is appended to the end of the heap's array representation.**Comparison**: The newly added element is compared with its parent node.**Swapping**: If the new element violates the heap property (i.e., it's larger than its parent in a max-heap or smaller in a min-heap), it is swapped with its parent. This process continues until the element is positioned correctly or reaches the root.

### Heapify Up Example

### Heap Operations: Heapify Down

To remove an element from a heap, the root element (either the largest in a max-heap or the smallest in a min-heap) is replaced by the last element, followed by "heapify down."

**Replacement**: The last element is moved to the root position.**Comparison**: The new root is compared with its children.**Swapping**: If the new root is smaller (in a max-heap) or larger (in a min-heap) than its children, it is swapped, and this process repeats until the element reaches a suitable position.

### Heapify Down Example

### Code Implementation of a Min-Heap

Here’s a simple implementation of a min-heap in Python:

class MinHeap:

def __init__(self):

self.heap: list[int] = []

def get_parent(self, i: int) -> int:

return (i - 1) // 2

def get_left_child(self, i: int) -> int:

return 2 * i + 1

def get_right_child(self, i: int) -> int:

return 2 * i + 2

def insert(self, value: int) -> None:

self.heap.append(value)

self.heapify_up(len(self.heap) - 1)

def heapify_up(self, index: int) -> None:

while index > 0 and self.heap[index] < self.heap[self.get_parent(index)]:

parent = self.get_parent(index)

self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]

index = parent

def remove(self) -> int | None:

if not self.heap:

return None

min_value = self.heap[0]

last_element = self.heap.pop()

if self.heap:

self.heap[0] = last_element

self.heapify_down(0)

return min_value

def heapify_down(self, index) -> None:

smallest = index

left_child = self.get_left_child(index)

right_child = self.get_right_child(index)

size = len(self.heap)

if left_child < size and self.heap[left_child] < self.heap[smallest]:

smallest = left_child

if right_child < size and self.heap[right_child] < self.heap[smallest]:

smallest = right_child

if smallest != index:

self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]

self.heapify_down(smallest)

Now, let's illustrate how the min-heap operates.

priority_queue = MinHeap()

priority_queue.insert(50)

priority_queue.insert(71)

priority_queue.insert(100)

priority_queue.insert(200)

priority_queue.insert(201)

priority_queue.insert(105)

heap = priority_queue.heap

50

/71 100

/ /

200 201 105

print(heap[0], heap[1], heap[2], heap[3], heap[4], heap[5])

After inserting a new element:

priority_queue.insert(3)

3

/71 50

/ /

200 201 105 100

print(heap[0], heap[1], heap[2], heap[3], heap[4], heap[5], heap[6])

Upon removing the root element:

priority_queue.remove()

50

/71 100

/ /

200 201 105

print(heap[0], heap[1], heap[2], heap[3], heap[4], heap[5])

### Time Complexity

- Insertion: O(log n)
- Deletion: O(log n)
- Finding maximum/minimum: O(1)

### Space Complexity

- Overall: O(n)

## Video Resources

To further explore heaps and their implementation, check out these insightful videos:

### Mastering DSA in C++ for Placements | Session 30: Heap Code Implementation

This video provides a detailed explanation and implementation of heaps in C++.

### How To Learn Data Structures & Algorithms In 30 Days | DSA 30 Day Roadmap

A comprehensive roadmap to mastering data structures and algorithms in just 30 days.