Help program, in Java Implement a version of heapsort based on complete heap-ord

Question

Help program, in Java

Implement a version of heapsort based on complete heap-ordered 3-ary as described in the text. Test your implementation using 100 randomly ordered distinct keys.

Explanation / Answer

import java.util.Scanner; /* Class HeapSort */ public class HeapSort { private static int N; /* Sort Function */ public static void sort(int arr[]) { heapify(arr); for (int i = N; i > 0; i--) { swap(arr,0, i); N = N-1; maxheap(arr, 0); } } /* Function to build a heap */ public static void heapify(int arr[]) { N = arr.length-1; for (int i = N/2; i >= 0; i--) maxheap(arr, i); } /* Function to swap largest element in heap */ public static void maxheap(int arr[], int i) { int left = 2*i ; int right = 2*i + 1; int max = i; if (left arr[i]) max = left; if (right arr[max]) max = right; if (max != i) { swap(arr, i, max); maxheap(arr, max); } } /* Function to swap two numbers in an array */ public static void swap(int arr[], int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } /* Main method */ public static void main(String[] args) { Scanner scan = new Scanner( System.in ); System.out.println("Heap Sort Test "); int n, i; /* Accept number of elements */ System.out.println("Enter number of integer elements"); n = scan.nextInt(); /* Make array of n elements */ int arr[] = new int[ n ]; /* Accept elements */ System.out.println(" Enter "+ n +" integer elements"); for (i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.