Peek operation on Max-heap Data Structure

4. Heapify operation on Max-heap Data Structure:

To access the maximum element (i.e., the root of the heap), the value of the root node is returned. The time complexity of peek in a max heap is O(1).

Peak Element Of Max- Heap

Implementation of Peek operation in Max-Heap:

C++

#include <iostream>
#include <queue>
 
int main() {
    // Create a max heap with some elements using a priority_queue
    std::priority_queue<int> maxHeap;
    maxHeap.push(9);
    maxHeap.push(8);
    maxHeap.push(7);
    maxHeap.push(6);
    maxHeap.push(5);
    maxHeap.push(4);
    maxHeap.push(3);
    maxHeap.push(2);
    maxHeap.push(1);
 
    // Get the peak element (i.e., the largest element)
    int peakElement = maxHeap.top();
 
    // Print the peak element
    std::cout << "Peak element: " << peakElement << std::endl;
 
    return 0;
}

Java

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> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.add(9);
        maxHeap.add(8);
        maxHeap.add(7);
        maxHeap.add(6);
        maxHeap.add(5);
        maxHeap.add(4);
        maxHeap.add(3);
        maxHeap.add(2);
        maxHeap.add(1);
 
        // Get the peak element (i.e., the largest element)
        int peakElement = maxHeap.peek();
 
        // Print the peak element
        System.out.println("Peak element: " + peakElement);
    }
}

C#

using System;
using System.Collections.Generic;
 
public class GFG {
    public static void Main() {
        // Create a min heap with some elements using a PriorityQueue
        var maxHeap = new PriorityQueue<int>();
        maxHeap.Enqueue(9);
        maxHeap.Enqueue(8);
        maxHeap.Enqueue(7);
        maxHeap.Enqueue(6);
        maxHeap.Enqueue(5);
        maxHeap.Enqueue(4);
        maxHeap.Enqueue(3);
        maxHeap.Enqueue(2);
        maxHeap.Enqueue(1);
 
        // Get the peak element (i.e., the smallest element)
        int peakElement = maxHeap.Peek();
 
        // Print the peak element
        Console.WriteLine("Peak element: " + peakElement);
    }
}
// Define a PriorityQueue class that uses a max heap
class PriorityQueue<T> where T : IComparable<T> {
    private List<T> heap;
 
    public PriorityQueue() {
        this.heap = new List<T>();
    }
 
    public int Count {
        get { return this.heap.Count; }
    }
 
    public void Enqueue(T item) {
        this.heap.Add(item);
        this.BubbleUp(this.heap.Count - 1);
    }
 
    public T Dequeue() {
        T item = this.heap[0];
        int lastIndex = this.heap.Count - 1;
        this.heap[0] = this.heap[lastIndex];
        this.heap.RemoveAt(lastIndex);
        this.BubbleDown(0);
        return item;
    }
 
    public T Peek() {
        return this.heap[0];
    }
 
    private void BubbleUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (this.heap[parentIndex].CompareTo(this.heap[index]) >= 0) {
                break;
            }
            Swap(parentIndex, index);
            index = parentIndex;
        }
    }
 
    private void BubbleDown(int index) {
        while (index < this.heap.Count) {
            int leftChildIndex = index * 2 + 1;
            int rightChildIndex = index * 2 + 2;
            int largestChildIndex = index;
            if (leftChildIndex < this.heap.Count && this.heap[leftChildIndex].CompareTo(this.heap[largestChildIndex]) > 0) {
                largestChildIndex = leftChildIndex;
            }
            if (rightChildIndex < this.heap.Count && this.heap[rightChildIndex].CompareTo(this.heap[largestChildIndex]) > 0) {
                largestChildIndex = rightChildIndex;
            }
            if (largestChildIndex == index) {
                break;
            }
            Swap(largestChildIndex, index);
            index = largestChildIndex;
        }
    }
 
    private void Swap(int i, int j) {
        T temp = this.heap[i];
        this.heap[i] = this.heap[j];
        this.heap[j] = temp;
    }
}

Javascript

// Define a MaxHeap class that uses an array
class MaxHeap {
    constructor() {
        this.heap = [];
    }
 
    push(item) {
        this.heap.push(item);
        this.bubbleUp(this.heap.length - 1);
    }
 
    pop() {
        let item = this.heap[0];
        let lastIndex = this.heap.length - 1;
        this.heap[0] = this.heap[lastIndex];
        this.heap.pop();
        this.bubbleDown(0);
        return item;
    }
 
    peak() {
        return this.heap[0];
    }
 
    bubbleUp(index) {
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) {
                break;
            }
            this.swap(parentIndex, index);
            index = parentIndex;
        }
    }
 
    bubbleDown(index) {
        while (index < this.heap.length) {
            let leftChildIndex = index * 2 + 1;
            let rightChildIndex = index * 2 + 2;
            let largestChildIndex = index;
            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[largestChildIndex]) {
                largestChildIndex = leftChildIndex;
            }
            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[largestChildIndex]) {
                largestChildIndex = rightChildIndex;
            }
            if (largestChildIndex === index) {
                break;
            }
            this.swap(largestChildIndex, index);
            index = largestChildIndex;
        }
    }
 
    swap(i, j) {
        let temp = this.heap[i];
        this.heap[i] = this.heap[j];
        this.heap[j] = temp;
    }
}
 
// Create a max heap with some elements using an array
let maxHeap = new MaxHeap();
maxHeap.push(9);
maxHeap.push(8);
maxHeap.push(7);
maxHeap.push(6);
maxHeap.push(5);
maxHeap.push(4);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(1);
 
// Get the peak element (i.e., the largest element)
let peakElement = maxHeap.peak();
 
// Print the peak element
console.log("Peak element: " + peakElement);

Python3

import heapq
 
# Create a max heap with some elements using a list
max_heap = [1,2,3,4,5,6,7,8,9]
heapq.heapify(max_heap)
 
# Get the peak element (i.e., the largest element)
peak_element = heapq.nlargest(1, max_heap)[0]
 
# Print the peak element
print("Peak element:", peak_element)

Output

Peak element: 9

Time complexity:

In a max 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 max 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 Max-Heap – Data Structure and Algorithm Tutorials

A Max-Heap is defined as a type of Heap Data Structure in which each internal node is greater 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 Max-Heap Data Structure

Purpose and Use Cases of Max-Heap:

Priority Queue: One of the primary uses of the heap data structure is for implementing priority queues.

Heap Sort: The heap data structure is also used in sorting algorithms.

Memory Management: The heap data structure is also used in memory management. When a program needs to allocate memory dynamically, it uses the heap data structure to keep track of the available memory.

Graph Algorithms: The heap data structure is used in various graph algorithms. For example, Dijkstra’s shortest path algorithm uses a heap data structure to keep track of the vertices with the shortest path from the source vertex.