Search operation on Min-Heap Data Structure
To search for an element in the min heap, a linear search can be performed over the array that represents the heap. However, the time complexity of a linear search is O(n), which is not efficient. Therefore, searching is not a commonly used operation in a min heap.
Here’s an example code that shows how to search for an element in a min heap using std::find():
#include <bits/stdc++.h>
using namespace std;
int main()
{
priority_queue<int, vector<int>, greater<int> >
min_heap;
// example max heap
min_heap.push(10);
min_heap.push(9);
min_heap.push(8);
min_heap.push(6);
min_heap.push(4);
int element = 6; // element to search for
bool found = false;
// Copy the min heap to a temporary queue and search for
// the element
std::priority_queue<int, vector<int>, greater<int> >
temp = min_heap;
while (!temp.empty()) {
if (temp.top() == element) {
found = true;
break;
}
temp.pop();
}
if (found) {
std::cout << "Element found in the min heap."
<< std::endl;
}
else {
std::cout << "Element not found in the min heap."
<< std::endl;
}
return 0;
}
import java.util.PriorityQueue;
public class GFG {
public static void main(String[] args)
{
PriorityQueue<Integer> min_heap
= new PriorityQueue<>();
min_heap.add(
3); // insert elements into the priority queue
min_heap.offer(1);
min_heap.offer(4);
min_heap.offer(1);
min_heap.offer(6);
int element = 6; // element to search for
boolean found = false;
// Copy the min heap to a temporary queue and search
// for the element
PriorityQueue<Integer> temp
= new PriorityQueue<>(min_heap);
while (!temp.isEmpty()) {
if (temp.poll() == element) {
found = true;
break;
}
}
if (found) {
System.out.println(
"Element found in the min heap.");
}
else {
System.out.println(
"Element not found in the min heap.");
}
}
}
import heapq
min_heap = [1, 2, 3, 5, 6, 7, 8, 10] # example min heap
heapq.heapify(min_heap)
element = 6 # element to search for
found = False
# Copy the min heap to a temporary list and search for the element
temp = list(min_heap)
while temp:
if heapq.heappop(temp) == element:
found = True
break
if found:
print("Element found in the min heap.")
else:
print("Element not found in the min heap.")
using System;
using System.Collections.Generic;
public class GFG {
public static void Main()
{
var minHeap = new PriorityQueue<int>();
// example min heap
minHeap.Enqueue(4);
minHeap.Enqueue(6);
minHeap.Enqueue(8);
minHeap.Enqueue(9);
minHeap.Enqueue(10);
int element = 6; // element to search for
bool found = false;
// Copy the min heap to a temporary queue and search
// for the element
var temp = new PriorityQueue<int>(minHeap);
while (temp.Count > 0) {
if (temp.Peek() == element) {
found = true;
break;
}
temp.Dequeue();
}
if (found) {
Console.WriteLine(
"Element found in the min heap.");
}
else {
Console.WriteLine(
"Element not found in the min heap.");
}
}
}
// Example min heap
let minHeap = new PriorityQueue();
minHeap.enqueue(4);
minHeap.enqueue(6);
minHeap.enqueue(8);
minHeap.enqueue(9);
minHeap.enqueue(10);
let element = 6; // Element to search for
let found = false;
// Copy the min heap to a temporary queue and search for the element
let temp = new PriorityQueue(minHeap);
while (temp.size() > 0) {
if (temp.peek() == element) {
found = true;
break;
}
temp.dequeue();
}
if (found) {
console.log("Element found in the min heap.");
} else {
console.log("Element not found in the min heap.");
}
Output
Element found in the min heap.
Complexity Analysis:
The time complexity of this program is O(n log n), where n is the number of elements in the priority queue.
The insertion operation has a time complexity of O(log n) in the worst case because the heap property needs to be maintained. The search operation involves copying the priority queue to a temporary queue and then traversing the temporary queue, which takes O(n log n) time in the worst case because each element needs to be copied and popped from the queue, and the priority queue needs to be rebuilt for each operation.
The space complexity of the program is O(n) because it stores n elements in the priority queue and creates a temporary queue with n elements.
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.
Introduction to Min-Heap – Data Structure and Algorithm Tutorials
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.
Contact Us