Skip to content
Gallery
Data Structures and Algorithms
Data Structures and Algorithms
Share
Explore
Heap & Priority Queue

Min-Heap & Max-Heap

Understanding the Differences Between Min-Heap and Max-Heap

In this section, we will explore the differences between Min-Heap and Max-Heap by comparing their implementations side by side. Both data structures share similar operations, but the way they maintain their heap properties (ordering of elements) differs. We'll walk through the key operations and methods for both Min-Heap and Max-Heap, highlighting the differences in their implementation.

1. Heap Property

Min-Heap: The parent node is always smaller than or equal to its child nodes. This ensures that the smallest element is always at the root.
Max-Heap: The parent node is always greater than or equal to its child nodes. This ensures that the largest element is always at the root.

2. Initialization and Heapification

Both Min-Heap and Max-Heap require an initial heapification process to ensure the heap property is maintained after creating the heap from an unordered list.

Min-Heap Initialization:

function MinHeap(list) {
heapList = list
buildMinHeap()
}

function buildMinHeap() {
for (i = floor(size of heapList / 2); i >= 0; i--) {
siftDownMin(i)
}
}

Max-Heap Initialization:

function MaxHeap(list) {
heapList = list;
buildMaxHeap();
}

function buildMaxHeap() {
for (int i = floor(size of heapList / 2); i >= 0; i--) {
siftDownMax(i);
}
}
Key Difference: The siftDown function in Min-Heap and Max-Heap differs in the comparison logic.

3. Sift Down Operation

The siftDown operation ensures that the heap property is maintained by moving a node downwards in the heap if it violates the heap property.

Min-Heap Sift Down:

function siftDownMin(i) {
left = 2 * i + 1
right = 2 * i + 2
while (left < size of heapList) {
smallest = i
if (heapList[left] < heapList[smallest]) {
smallest = left
}
if (right < size of heapList and heapList[right] < heapList[smallest]) {
smallest = right
}
if (smallest == i) {
break
}
swap(heapList, i, smallest)
i = smallest
left = 2 * i + 1
right = 2 * i + 2
}
}

Max-Heap Sift Down:

function siftDownMax(i) {
left = 2 * i + 1
right = 2 * i + 2
while (left < size of heapList) {
largest = i
if (heapList[left] > heapList[largest]) {
largest = left
}
if (right < size of heapList and heapList[right] > heapList[largest]) {
largest = right
}
if (largest == i) {
break
}
swap(heapList, i, largest)
i = largest
left = 2 * i + 1
right = 2 * i + 2
}
}
Key Difference: In Min-Heap, we compare the node with the smallest child, while in Max-Heap, we compare it with the largest child.

4. Sift Up Operation

The siftUp operation restores the heap property by moving a node upwards if necessary.

Min-Heap Sift Up:

function siftUpMin(i) {
parent = (i-1) // 2
while (i > 0 and heapList[i] < heapList[parent]) {
swap(heapList, i, parent)
i = parent
parent = (i-1) // 2
}
}

Max-Heap Sift Up:

function siftUpMax(i) {
parent = (i-1) // 2
while (i > 0 and heapList[i] > heapList[parent]) {
swap(heapList, i, parent)
i = parent
parent = (i-1) // 2
}
}
Key Difference: The comparison in siftUp for Min-Heap checks if the current node is smaller than the parent, while in Max-Heap, it checks if the current node is larger.

5. Insertion

Insertion involves adding a new element to the heap and then restoring the heap property by performing a siftUp.

Min-Heap Insertion:

function insertMin(num) {
append num to heapList
siftUpMin(size of heapList - 1)
}

Max-Heap Insertion:

function insertMax(num) {
append num to heapList
siftUpMax(size of heapList - 1)
}
Key Difference: The insertion operation uses either siftUpMin or siftUpMax depending on the type of heap.

6. Extracting the Root (Minimum/Maximum)

Extracting the root involves removing the top element (smallest in Min-Heap, largest in Max-Heap) and then restoring the heap property by performing a siftDown.

Min-Heap Extract Min:

function extractMin() {
if (size of heapList == 0) {
return null
}
minVal = heapList[0]
heapList[0] = heapList[size of heapList - 1]
remove last element from heapList
siftDownMin(0)
return minVal
}

Max-Heap Extract Min:

function extractMax() {
if (size of heapList == 0) {
return null
}
maxVal = heapList[0]
heapList[0] = heapList[size of heapList - 1]
remove last element from heapList
siftDownMax(0)
return maxVal
}
Key Difference: The extraction operation involves siftDownMin for Min-Heap and siftDownMax for Max-Heap.

7. Updating a Node

Updating a node's value involves adjusting its position in the heap, either by siftUp or siftDown depending on whether the new value is smaller or larger.

Min-Heap Update:

function updateMin(i, newValue) {
oldValue = heapList[i]
heapList[i] = newValue
if (newValue < oldValue) {
siftUpMin(i)
} else {
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.