Scribd
Upload
8 views3 pages

DAA

Data analytist and algo

Uploaded by

Aayush Kharkia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

DAA

Data analytist and algo

Uploaded by

Aayush Kharkia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Deletion of Maximum Element in a Max-Heap Tree:

In a max-heap, the maximum element is always at the root. Deleting the maximum element involves removing the root node and then reorganizing the heap to maintain the max-heap property.

Here are the steps to delete the maximum element from a max-heap:

Replace Root with Last Element:

To delete the maximum element, we replace the root (maximum element) with the last element of the heap.

Remove Last Element:

After replacing the root, we remove the last element from the heap. This ensures that the heap remains complete.

Restore Max-Heap Property:

After replacing the root, the max-heap property might be violated. We need to restore this property by performing a heapify operation.

Heapify Operation:

Starting from the root, we compare the parent node with its children. We swap the parent node with the larger child (if the parent is smaller than its children) until the max-heap property is restored.

code:

#include <stdio.h>

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temp;

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1; // left = 2*i + 1

int right = 2 * i + 2; // right = 2*i + 2

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(&arr[i], &arr[largest]);

heapify(arr, n, largest);

int deleteMax(int arr[], int *n) {

if (*n <= 0) // Heap is empty

return -1;

if (*n == 1) { // Only one element in heap

(*n)--;

1
return arr[0];

int maxElement = arr[0];

arr[0] = arr[*n - 1];

(*n)--;

heapify(arr, *n, 0);

return maxElement;

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = { 10, 20, 15, 30, 40 };

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

int deletedElement = deleteMax(arr, &n);

if (deletedElement != -1)

printf("Maximum element deleted: %d\n", deletedElement);

else

printf("Heap is empty, deletion failed.\n");

printf("Array after deletion: ");

printArray(arr, n);

return 0;

Binary search is a fundamental algorithm used to search for a specific element in a sorted array efficiently.

Binary search is an efficient algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing in half the portion of the array that could contain the target value, and then
comparing the target value with the middle element of the resulting subarray.

Initialize: Start with the entire sorted array.

Compare: Compare the target value with the middle element of the array.

Divide: If the target value matches the middle element, return its index. If the target value is less than the middle element, continue the search on the left half of the array. If the target value is greater,
continue the search on the right half.

Repeat: Repeat the process until the target value is found or the subarray is empty.

Terminate: If the target value is not found after the entire array is searched, return a "not found" indication.

The time complexity of binary search is O(log n), where n is the number of elements in the array. This is because, with each comparison, the size of the search space is halved. Therefore, binary search is highly

2
efficient for large sorted arrays.

You might also like