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."

1. Placement: The new element is appended to the end of the heap's array representation.
2. Comparison: The newly added element is compared with its parent node.
3. 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."

1. Replacement: The last element is moved to the root position.
2. Comparison: The new root is compared with its children.
3. 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)

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.