Peek operation on Min-Heap Data Structure
To access the minimum element (i.e., the root of the heap), the value of the root node is returned. The time complexity of peek in a min-heap is O(1).
Implementation of Peek operation in Min-Heap:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
// Create a max heap with some elements using a
// priority_queue
priority_queue<int, vector<int>, greater<int> > minHeap;
minHeap.push(9);
minHeap.push(8);
minHeap.push(7);
minHeap.push(6);
minHeap.push(5);
minHeap.push(4);
minHeap.push(3);
minHeap.push(2);
minHeap.push(1);
// Get the peak element (i.e., the largest element)
int peakElement = minHeap.top();
// Print the peak element
cout << "Peak element: " << peakElement << std::endl;
return 0;
}
import java.util.PriorityQueue;
public class GFG {
public static void main(String[] args)
{
// Create a max heap with some elements using a
// PriorityQueue
PriorityQueue<Integer> minHeap
= new PriorityQueue<>();
minHeap.add(9);
minHeap.add(8);
minHeap.add(7);
minHeap.add(6);
minHeap.add(5);
minHeap.add(4);
minHeap.add(3);
minHeap.add(2);
minHeap.add(1);
// Get the peak element (i.e., the largest element)
int peakElement = minHeap.peek();
// Print the peak element
System.out.println("Peak element: " + peakElement);
}
}
import heapq
# Create a min heap with some elements using a list
min_heap = [9, 8, 7, 6, 5, 4, 3, 2, 1]
heapq.heapify(min_heap)
# Get the peak element (i.e., the smallest element)
peak_element = heapq.nsmallest(1, min_heap)[0]
# Print the peak element
print("Peak element:", peak_element)
using System;
using System.Collections.Generic;
public class GFG {
public static void Main()
{
// Create a min heap with some elements using a
// PriorityQueue
var minHeap = new PriorityQueue<int>();
minHeap.Enqueue(9);
minHeap.Enqueue(8);
minHeap.Enqueue(7);
minHeap.Enqueue(6);
minHeap.Enqueue(5);
minHeap.Enqueue(4);
minHeap.Enqueue(3);
minHeap.Enqueue(2);
minHeap.Enqueue(1);
// Get the peak element (i.e., the smallest element)
int peakElement = minHeap.Peek();
// Print the peak element
Console.WriteLine("Peak element: " + peakElement);
}
}
const PriorityQueue = require('fast-priority-queue');
// Create a min heap with some elements using a PriorityQueue
const minHeap = new PriorityQueue((a, b) => a - b);
minHeap.add(9);
minHeap.add(8);
minHeap.add(7);
minHeap.add(6);
minHeap.add(5);
minHeap.add(4);
minHeap.add(3);
minHeap.add(2);
minHeap.add(1);
// Get the peak element (i.e., the smallest element)
const peakElement = minHeap.peek();
// Print the peak element
console.log(`Peak element: ${peakElement}`);
Output
Peak element: 1
Time complexity: In a min heap implemented using an array or a list, the peak element can be accessed in constant time, O(1), as it is always located at the root of the heap.
In a min heap implemented using a binary tree, the peak element can also be accessed in O(1) time, as it is always located at the root of the tree.
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.