WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Heap Sort Algorithms
Introduction to Heap Sort
Heap sort is a comparison-based sorting technique based on a binary heap data structure. It is similar to selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.
Example 1: Basic Heap Sort
Understanding Basic Heap Sort
In a basic heap sort, we build a max heap from the input data. The largest item is stored at the root of the heap. We then replace it with the last item of the heap followed by reducing the size of the heap by one. The heapifying process is then applied to the root again.
import java.util.Arrays;
class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
System.out.println(Arrays.toString(arr));
}
}
Console Output:
Sorted array is [5, 6, 7, 11, 12, 13]
Example 2: Min Heap Sort
Min Heap Sort Explanation
Min heap sort is similar to max heap sort, but instead of finding the largest element first, we find the smallest element and move it to the beginning of the array.
import java.util.Arrays;
class MinHeapSort {
public void sort(int arr[]) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
for (int i=n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
minHeapify(arr, i, 0);
}
}
void minHeapify(int arr[], int n, int i) {
int smallest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] < arr[smallest])
smallest = l;
if (r < n && arr[r] < arr[smallest])
smallest = r;
if (smallest != i) {
int swap = arr[i];
arr[i] = arr[smallest];
arr[smallest] = swap;
minHeapify(arr, n, smallest);
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
MinHeapSort ob = new MinHeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
System.out.println(Arrays.toString(arr));
}
}
Console Output:
Sorted array is [13, 12, 11, 7, 6, 5]
Example 3: Heap Sort with Custom Objects
Sorting Custom Objects
Heap sort can also be applied to custom objects by using a comparator to define the order of the elements.
import java.util.Arrays;
import java.util.Comparator;
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return name + ": " + age;
}
}
class PersonHeapSort {
public void sort(Person arr[], Comparator comparator) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i, comparator);
for (int i=n-1; i>=0; i--) {
Person temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0, comparator);
}
}
void heapify(Person arr[], int n, int i, Comparator comparator) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && comparator.compare(arr[l], arr[largest]) > 0)
largest = l;
if (r < n && comparator.compare(arr[r], arr[largest]) > 0)
largest = r;
if (largest != i) {
Person swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest, comparator);
}
}
public static void main(String args[]) {
Person arr[] = {new Person("Alice", 23), new Person("Bob", 34), new Person("Charlie", 29)};
int n = arr.length;
PersonHeapSort ob = new PersonHeapSort();
ob.sort(arr, Comparator.comparingInt(o -> o.age));
System.out.println("Sorted array is");
System.out.println(Arrays.toString(arr));
}
}
Console Output:
Sorted array is [Alice: 23, Charlie: 29, Bob: 34]
Example 4: Iterative Heap Sort
Iterative Approach
Instead of using recursion, heap sort can be implemented iteratively to avoid stack overflow issues for large datasets.
import java.util.Arrays;
class IterativeHeapSort {
public void sort(int arr[]) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
iterativeHeapify(arr, n, i);
for (int i=n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
iterativeHeapify(arr, i, 0);
}
}
void iterativeHeapify(int arr[], int n, int i) {
while (i < n) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
i = largest;
} else {
break;
}
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
IterativeHeapSort ob = new IterativeHeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
System.out.println(Arrays.toString(arr));
}
}
Console Output:
Sorted array is [5, 6, 7, 11, 12, 13]
Example 5: Parallel Heap Sort
Parallel Processing
Heap sort can be parallelized to improve performance on multi-core systems. This involves dividing the array into segments and sorting them concurrently.
// Note: This is a conceptual representation as Java does not natively support parallel heap sort.
import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
class ParallelHeapSort {
public void sort(int arr[]) {
ExecutorService executor = Executors.newFixedThreadPool(2);
int mid = arr.length / 2;
executor.execute(() -> heapSortSegment(arr, 0, mid));
executor.execute(() -> heapSortSegment(arr, mid, arr.length));
executor.shutdown();
while (!executor.isTerminated()) {}
merge(arr, 0, mid, arr.length);
}
private void heapSortSegment(int[] arr, int start, int end) {
for (int i = (end + start) / 2 - 1; i >= start; i--)
heapify(arr, end, i);
for (int i = end - 1; i >= start; i--) {
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
heapify(arr, i, start);
}
}
private void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
private void merge(int[] arr, int left, int mid, int right) {
int[] leftArray = Arrays.copyOfRange(arr, left, mid);
int[] rightArray = Arrays.copyOfRange(arr, mid, right);
int i = 0, j = 0, k = left;
while (i < leftArray.length && j < rightArray.length) {
if (leftArray[i] <= rightArray[j]) {
arr[k++] = leftArray[i++];
} else {
arr[k++] = rightArray[j++];
}
}
while (i < leftArray.length) {
arr[k++] = leftArray[i++];
}
while (j < rightArray.length) {
arr[k++] = rightArray[j++];
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
ParallelHeapSort ob = new ParallelHeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
System.out.println(Arrays.toString(arr));
}
}
Console Output:
Sorted array is [5, 6, 7, 11, 12, 13]
