”;
Heapify method rearranges the elements of an array where the left and right sub-tree of ith element obeys the heap property.
Heapify Pseudocode
Max-Heapify(numbers[], i) leftchild := numbers[2i] rightchild := numbers [2i + 1] if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] largest := leftchild else largest := i if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] largest := rightchild if largest ≠ i swap numbers[i] with numbers[largest] Max-Heapify(numbers, largest)
When the provided array does not obey the heap property, Heap is built based on the following algorithm Build-Max-Heap (numbers[]).
Algorithm: Build-Max-Heap(numbers[]) numbers[].size := numbers[].length fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 Max-Heapify (numbers[], i)
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void maxHeapify(int arr[], int size, int i) {
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
int largest = i;
if (leftChild < size && arr[leftChild] > arr[largest])
largest = leftChild;
if (rightChild < size && arr[rightChild] > arr[largest])
largest = rightChild;
if (largest != i) {
swap(arr, i, largest);
maxHeapify(arr, size, largest); // Recursive call to continue heapifying
}
}
void buildMaxHeap(int arr[], int size) {
for (int i = size / 2 - 1; i >= 0; i--)
maxHeapify(arr, size, i); // Start heapifying from the parent nodes in bottom-up order
}
int main() {
int arr[] = { 3, 10, 4, 5, 1 }; // Initial Max-Heap (or any array)
int size = sizeof(arr) / sizeof(arr[0]);
buildMaxHeap(arr, size); // Build the Max-Heap from the given array
printf("Max Heap: ");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]); // Print the updated Max-Heap
printf("n");
return 0;
}
Output
Max Heap: 10 5 4 3 1
#include <iostream>
#include <vector>
using namespace std;
void swap(vector<int>& arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void maxHeapify(vector<int>& arr, int size, int i) {
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
int largest = i;
if (leftChild < size && arr[leftChild] > arr[largest])
largest = leftChild;
if (rightChild < size && arr[rightChild] > arr[largest])
largest = rightChild;
if (largest != i) {
swap(arr, i, largest);
maxHeapify(arr, size, largest); // Recursive call to continue heapifying
}
}
void buildMaxHeap(vector<int>& arr, int size) {
for (int i = size / 2 - 1; i >= 0; i--)
maxHeapify(arr, size, i); // Start heapifying from the parent nodes in bottom-up order
}
int main() {
vector<int> arr = { 3, 10, 4, 5, 1 }; // Initial Max-Heap (or any array)
int size = arr.size();
buildMaxHeap(arr, size); // Build the Max-Heap from the given array
cout << "Max Heap: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " "; // Print the updated Max-Heap
cout << endl;
return 0;
}
Output
Max Heap: 10 5 4 3 1
import java.util.Arrays;
public class MaxHeap {
public static void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void maxHeapify(int arr[], int size, int i) {
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
int largest = i;
if (leftChild < size && arr[leftChild] > arr[largest])
largest = leftChild;
if (rightChild < size && arr[rightChild] > arr[largest])
largest = rightChild;
if (largest != i) {
swap(arr, i, largest);
maxHeapify(arr, size, largest); // Recursive call to continue heapifying
}
}
public static void buildMaxHeap(int arr[]) {
int size = arr.length;
for (int i = size / 2 - 1; i >= 0; i--)
maxHeapify(arr, size, i); // Start heapifying from the parent nodes in bottom-up order
}
public static void main(String args[]) {
int arr[] = { 3, 10, 4, 5, 1 }; // Initial Max-Heap (or any array)
buildMaxHeap(arr); // Build the Max-Heap from the given array
System.out.print("Max Heap: ");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " "); // Print the updated Max-Heap
System.out.println();
}
}
Output
Max Heap: 10 5 4 3 1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def max_heapify(arr, size, i):
left_child = 2 * i + 1
right_child = 2 * i + 2
largest = i
if left_child < size and arr[left_child] > arr[largest]:
largest = left_child
if right_child < size and arr[right_child] > arr[largest]:
largest = right_child
if largest != i:
swap(arr, i, largest)
max_heapify(arr, size, largest) # Recursive call to continue heapifying
def build_max_heap(arr):
size = len(arr)
for i in range(size // 2 - 1, -1, -1):
max_heapify(arr, size, i) # Start heapifying from the parent nodes in bottom-up order
arr = [3, 10, 4, 5, 1] # Initial Max-Heap (or any array)
build_max_heap(arr) # Build the Max-Heap from the given array
print("Max Heap:", arr) # Print the updated Max-Heap
Output
Max Heap: [10, 5, 4, 3, 1]
Advertisements
”;