Search operation on Max-heap Data Structure

4. Heapify operation on Max-heap Data Structure:

Applications of Max-Heap Data Structure:

To search for an element in the max 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 max heap.

Here’s an example code that shows how to search for an element in a max heap using std::find():

C++

#include <iostream>
#include <queue> // for std::priority_queue
using namespace std;
 
int main() {
    std::priority_queue<int> max_heap;
  // example max heap
   
  max_heap.push(10);
  max_heap.push(9);
  max_heap.push(8);
  max_heap.push(6);
  max_heap.push(4);
 
    int element = 6; // element to search for
    bool found = false;
 
    // Copy the max heap to a temporary queue and search for the element
    std::priority_queue<int> temp = max_heap;
    while (!temp.empty()) {
        if (temp.top() == element) {
            found = true;
            break;
        }
        temp.pop();
    }
 
    if (found) {
        std::cout << "Element found in the max heap." << std::endl;
    } else {
        std::cout << "Element not found in the max heap." << std::endl;
    }
 
    return 0;
}

Java

import java.util.PriorityQueue;
 
public class GFG {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.add(3); // insert elements into the priority queue
        maxHeap.offer(1);
        maxHeap.offer(4);
        maxHeap.offer(1);
        maxHeap.offer(6);
 
        int element = 6; // element to search for
        boolean found = false;
 
        // Copy the max heap to a temporary queue and search for the element
        PriorityQueue<Integer> temp = new PriorityQueue<>(maxHeap);
        while (!temp.isEmpty()) {
            if (temp.poll() == element) {
                found = true;
                break;
            }
        }
 
        if (found) {
            System.out.println("Element found in the max heap.");
        } else {
            System.out.println("Element not found in the max heap.");
        }
    }
}

C#

using System;
using System.Collections.Generic;
 
class Program {
    static void Main(string[] args) {
        // Create a max heap with some elements using a PriorityQueue
        PriorityQueue<int> maxHeap = new PriorityQueue<int>();
        maxHeap.Enqueue(10);
        maxHeap.Enqueue(9);
        maxHeap.Enqueue(8);
        maxHeap.Enqueue(6);
        maxHeap.Enqueue(4);
 
        int element = 6; // element to search for
        bool found = false;
 
        // Copy the max heap to a temporary queue and search for the element
        PriorityQueue<int> temp = new PriorityQueue<int>(maxHeap);
        while (temp.Count > 0) {
            if (temp.Peek() == element) {
                found = true;
                break;
            }
            temp.Dequeue();
        }
 
        if (found) {
            Console.WriteLine("Element found in the max heap.");
        } else {
            Console.WriteLine("Element not found in the max heap.");
        }
    }
}
 
// PriorityQueue class
class PriorityQueue<T> where T : IComparable<T> {
    private List<T> heap = new List<T>();
 
    public void Enqueue(T item) {
        heap.Add(item);
        int child = heap.Count - 1;
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (heap[child].CompareTo(heap[parent]) > 0) {
                T tmp = heap[child];
                heap[child] = heap[parent];
                heap[parent] = tmp;
                child = parent;
            } else {
                break;
            }
        }
    }
 
    public T Dequeue() {
        int last = heap.Count - 1;
        T frontItem = heap[0];
        heap[0] = heap[last];
        heap.RemoveAt(last);
 
        last--;
 
        int parent = 0;
        while (true) {
            int leftChild = parent * 2 + 1;
            if (leftChild > last) {
                break;
            }
            int rightChild = leftChild + 1;
            if (rightChild <= last && heap[leftChild].CompareTo(heap[rightChild]) < 0) {
                leftChild = rightChild;
            }
            if (heap[parent].CompareTo(heap[leftChild]) < 0) {
                T tmp = heap[parent];
                heap[parent] = heap[leftChild];
                heap[leftChild] = tmp;
                parent = leftChild;
            } else {
                break;
            }
        }
 
        return frontItem;
    }
 
    public T Peek() {
        return heap[0];
    }
 
    public int Count {
        get {
            return heap.Count;
        }
    }
}

Javascript

const maxHeap = new PriorityQueue((a, b) => b - a);
maxHeap.add(3); // insert elements into the priority queue
maxHeap.add(1);
maxHeap.add(4);
maxHeap.add(1);
maxHeap.add(6);
 
const element = 6; // element to search for
let found = false;
 
// Copy the max heap to a temporary queue and search for the element
const temp = new PriorityQueue(maxHeap);
while (!temp.isEmpty()) {
if (temp.poll() === element) {
found = true;
break;
}
}
 
if (found) {
console.log("Element found in the max heap.");
} else {
console.log("Element not found in the max heap.");
}

Python3

import heapq
 
max_heap = [10, 8, 7, 6, 5, 3, 2, 1] # example max heap
heapq._heapify_max(max_heap)
 
element = 6 # element to search for
found = False
 
# Copy the max heap to a temporary list and search for the element
temp = list(max_heap)
while temp:
    if heapq._heappop_max(temp) == element:
        found = True
        break
 
if found:
    print("Element found in the max heap.")
else:
    print("Element not found in the max heap.")

Output

Element found in the max heap.

Time complexity: O(n), where n is the size of the heap.
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.

Search operation on Max-heap Data Structure

C++

Java

C#

Javascript

Python3

Introduction to Max-Heap – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us