Insertion in Min-Heap Data Structure
Elements can be inserted into the heap following a similar approach as discussed above for deletion. The idea is to:
- The insertion operation in a min-heap involves the following steps:
- Add the new element to the end of the heap, in the next available position in the last level of the tree.
- Compare the new element with its parent. If the parent is greater than the new element, swap them.
- Repeat step 2 until the parent is smaller than or equal to the new element, or until the new element reaches the root of the tree.
- The new element is now in its correct position in the min heap, and the heap property is satisfied.
Illustration:
Suppose the Heap is a Min-Heap as:
Implementation of Insertion Operation in Min-Heap:
#include <iostream>
#include <vector>
using namespace std;
// Function to insert a new element into the min-heap
void insert_min_heap(vector<int>& heap, int value)
{
// Add the new element to the end of the heap
heap.push_back(value);
// Get the index of the last element
int index = heap.size() - 1;
// Compare the new element with its parent and swap if
// necessary
while (index > 0
&& heap[(index - 1) / 2] > heap[index]) {
swap(heap[index], heap[(index - 1) / 2]);
// Move up the tree to the parent of the current
// element
index = (index - 1) / 2;
}
}
// Main function to test the insert_min_heap function
int main()
{
vector<int> heap;
int values[] = { 10, 7, 11, 5, 4, 13 };
int n = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < n; i++) {
insert_min_heap(heap, values[i]);
cout << "Inserted " << values[i]
<< " into the min-heap: ";
for (int j = 0; j < heap.size(); j++) {
cout << heap[j] << " ";
}
cout << endl;
}
return 0;
}
import java.util.*;
public class GFG {
// Function to insert a new element into the min-heap
public static void insertMinHeap(int[] heap, int size,
int value)
{
// Add the new element to the end of the heap
heap[size] = value;
// Get the index of the last element
int index = size;
// Compare the new element with its parent and swap
// if necessary
while (index > 0
&& heap[(index - 1) / 2] > heap[index]) {
swap(heap, index, (index - 1) / 2);
// Move up the tree to the parent of the current
// element
index = (index - 1) / 2;
}
}
// Function to swap two elements in an array
public static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Main function to test the insertMinHeap function
public static void main(String[] args)
{
int[] heap = new int[6];
int[] values = { 10, 7, 11, 5, 4, 13 };
int size = 0;
for (int i = 0; i < values.length; i++) {
insertMinHeap(heap, size, values[i]);
size++;
System.out.print("Inserted " + values[i]
+ " into the min-heap: ");
for (int j = 0; j < size; j++) {
System.out.print(heap[j] + " ");
}
System.out.println();
}
}
}
def insert_min_heap(heap, value):
# Add the new element to the end of the heap
heap.append(value)
# Get the index of the last element
index = len(heap) - 1
# Compare the new element with its parent and swap if necessary
while index > 0 and heap[(index - 1) // 2] > heap[index]:
heap[index], heap[(index - 1) //
2] = heap[(index - 1) // 2], heap[index]
# Move up the tree to the parent of the current element
index = (index - 1) // 2
heap = []
values = [10, 7, 11, 5, 4, 13]
for value in values:
insert_min_heap(heap, value)
print(f"Inserted {value} into the min-heap: {heap}")
using System;
using System.Collections.Generic;
public class Program {
// Function to insert a new element into the min-heap
static void InsertMinHeap(List<int> heap, int value)
{
// Add the new element to the end of the heap
heap.Add(value);
// Get the index of the last element
int index = heap.Count - 1;
// Compare the new element with its parent and swap
// if necessary
while (index > 0
&& heap[(index - 1) / 2] > heap[index]) {
int temp = heap[index];
heap[index] = heap[(index - 1) / 2];
heap[(index - 1) / 2] = temp;
// Move up the tree to the parent of the current
// element
index = (index - 1) / 2;
}
}
// Main function to test the InsertMinHeap function
public static void Main()
{
List<int> heap = new List<int>();
int[] values = { 10, 7, 11, 5, 4, 13 };
foreach(int value in values)
{
InsertMinHeap(heap, value);
Console.Write("Inserted " + value
+ " into the min-heap: ");
foreach(int element in heap)
{
Console.Write(element + " ");
}
Console.WriteLine();
}
}
}
function insertMinHeap(heap, value) {
heap.push(value);
let index = heap.length - 1;
let parentIndex = Math.floor((index - 1) / 2);
while (index > 0 && heap[parentIndex] > heap[index]) {
[heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]];
index = parentIndex;
parentIndex = Math.floor((index - 1) / 2);
}
}
// Example usage
const heap = [];
const values = [10, 7, 11, 5, 4, 13];
for (const value of values) {
insertMinHeap(heap, value);
console.log(`Inserted ${value} into the min-heap: ${heap}`);
}
Output
Inserted 10 into the min-heap: 10 Inserted 7 into the min-heap: 7 10 Inserted 11 into the min-heap: 7 10 11 Inserted 5 into the min-heap: 5 7 11 10 Inserted 4 into the min-heap: 4 5 11 10 7 Inser...
Time Complexity: O(log(n)) (where n is no of elements in the heap)
Auxiliary Space: O(n)
Introduction to Min-Heap – Data Structure and Algorithm Tutorials
A Min-Heap is defined as a type of Heap Data Structure in which each node is smaller than or equal to its children.
The heap data structure is a type of binary tree that is commonly used in computer science for various purposes, including sorting, searching, and organizing data.
Purpose and Use Cases of Min-Heap:
- Implementing Priority Queue: One of the primary uses of the heap data structure is for implementing priority queues.
- Dijkstra’s Algorithm: Dijkstra’s algorithm is a shortest path algorithm that finds the shortest path between two nodes in a graph. A min heap can be used to keep track of the unvisited nodes with the smallest distance from the source node.
- Sorting: A min heap can be used as a sorting algorithm to efficiently sort a collection of elements in ascending order.
- Median finding: A min heap can be used to efficiently find the median of a stream of numbers. We can use one min heap to store the larger half of the numbers and one max heap to store the smaller half. The median will be the root of the min heap.