WikiGalaxy
Heapify Process
Understanding Heapify:
Heapify is a process used to create a heap data structure from a binary tree. It involves rearranging the elements to satisfy the heap property, which is crucial in implementing priority queues and heapsort algorithms.
Max-Heapify:
Max-Heapify ensures that the parent node is greater than or equal to its child nodes. This is essential for the correct functioning of a max-heap, where the maximum element is always at the root.
Min-Heapify:
Min-Heapify ensures that the parent node is less than or equal to its child nodes. This property is vital for a min-heap, where the minimum element is always at the root.
Building a Heap:
Building a heap involves applying the heapify process to all non-leaf nodes of a binary tree, starting from the bottom-most and right-most internal node and moving upwards to the root.
Heap Sort:
Heap Sort utilizes the heapify process to sort an array. It involves building a heap from the array and repeatedly extracting the maximum (or minimum) element to achieve a sorted order.
import java.util.Arrays;
class HeapifyExample {
public static void maxHeapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int 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) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
maxHeapify(arr, n, largest);
}
}
public static void buildMaxHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(arr, n, i);
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
buildMaxHeap(arr);
System.out.println("Max-Heap: " + Arrays.toString(arr));
}
}
Customizing Heap Behavior:
The heapify process can be customized for specific use cases, such as implementing a custom priority queue where elements have different priorities based on user-defined criteria.
Console Output:
Max-Heap: [10, 5, 3, 4, 1]
Min-Heapify Example
Min-Heapify Process:
The Min-Heapify process is similar to Max-Heapify but ensures that the smallest element is at the root. This is useful for implementing priority queues where the highest priority is the smallest number.
import java.util.Arrays;
class MinHeapifyExample {
public static void minHeapify(int[] arr, int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
int swap = arr[i];
arr[i] = arr[smallest];
arr[smallest] = swap;
minHeapify(arr, n, smallest);
}
}
public static void buildMinHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
buildMinHeap(arr);
System.out.println("Min-Heap: " + Arrays.toString(arr));
}
}
Applications of Min-Heap:
Min-heaps are used in applications like Dijkstra's algorithm for finding the shortest path in a graph, where the smallest element (shortest distance) needs to be accessed quickly.
Console Output:
Min-Heap: [1, 4, 3, 5, 10]
